Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[madk]

Manhattan is going to be the fastest, I suppose, but it isn't anything near accurate.


Anyway, someone recommended a while back to categorize items into general sections and check the items within the closer sections first. If this isn't done already, it certainly should be.


EDIT: That algorithm I described doesn't produce a circle, it produces a diamond. I'm fiddling with it a little to see if I can make something fair circular using only primitive math functions.

EDIT: Combining the algorithm and Manhattan distance would yield an octogon. Maybe that'll be useful to someone.

[Rafal99]

@madk: Programming related stuff.

Spoiler (click to show/hide)

Concerning dwarves searching for items, and checking distance to every item, if this is done that way, it should be optimized. Distance calculations should avoid sqrt() which is expensive if they don't already.

You can easily compare distances with acceptable accuracy just by using only addition, bitshifting, and Abs.

Example:
(Abs(Origin_X-Target_X) Shl 4) + (Abs(Origin_Y-Target_Y) Shl 4) + (Abs(Origin_Z-Target_Z) Shl 12)

Such comparison would be lightning fast, and would rarely assign a dwarf something that is a greater distance away. It would also help to prevent dwarves from thinking something directly above them that may or may not have nearby access is actually closer, though I do think Toady's got that covered with the current system.

How does it work?

Abs(X₁-X₂) makes the number positive. This operation is extremely fast, requiring only 3 opcodes on the x86. Abs(X₁-X₂) will henceforth be referred to as "A".

A Shl Y Is equivalent to A*2^Y. While this is far from a perfect linear distance, it would work
beautifully for mere comparisons. This operation is a single opcode on the x86.

And, lastly, adding the three A values for X, Y, and Z (shifting the bits farther left for the Z axis) is, very obviously, trivial.

Sorry for getting so technical, but if Toady sees this post, he must realize the awesomeness of this method.

ADD IT NOW, TARN! PLEASE!!
[/size]

Yeah what you described is Manhattan distance, it is an option too. Well I don't get why you shift all distances instead of Z only which you want to multiply, hmm... Also you can simply multiply or divide them by 2, 4 etc, compilers optimize these operations to bitshifts anyway as long as it is a power of 2.


What I meant in my earlier post is that with Euclidean distance instead of using:

dist = sqrt(xdist*xdist + ydist*ydist + zdist*zdist);
if (dist < minimumDist) {   //this item is closest so far, do stuff

You should use:

squareDist = xdist*xdist + ydist*ydist + zdist*zdist);
if (squareDist < minimumSquareDist) {  //this item is closest so far, do stuff

You avoid sqrt which is expensive (needs many iterations to calculate) and if you would use it in a loop iterating though 100000 items it may matter a lot.
Or use Manhattan distance instead, yeah.

[gtmattz]

4 things I do to save FPS:

• Embark on 3x3 or smaller areas. The new features really don't need any larger.
• Set up smart burrows to restrict accessibility and thus reduce pathfinding load.

• Use ramps instead of stairs whenever possible.

• Avoid large amounts of flowing liquids if possible.

The others are self explanatory but why does ramps instead of stairs help fps?

You know, I really have no idea, all I know is that when I start using a lot of stairs, especially shafts of stairs, that my FPS starts tanking.  I am assuming it is some kind of path-finding issue, but really haven't the slightest idea why it makes a difference, I just know that it does. sorry 

[madk]

The equation I described yields a diamond:

Code: [Select]

     X     
    XXX   
   XXXXX   
  XXXXXXX 
   XXXXX   
    XXX   
     X     
Manhattan distance is a rectangle.

Code: [Select]

  XXXXXXX 
  XXXXXXX 
  XXXXXXX 
  XXXXXXX 
  XXXXXXX 
  XXXXXXX 
  XXXXXXX 
If you combine them, you can get an octagon, which is pretty darn close to a circle, and requires staggeringly less computation than using sqrt.

Code: [Select]

           
    XXX   
   XXXXX   
   XXXXX   
   XXXXX   
    XXX   
           
- Using a minimum Manhattan distance of 2 and making sure my algorithm shifts left once and considers only the XY plane with a minimum distance of 8. Shifting multiple times increases the "distance" on said axis at any given truly linear distance. For example, shifting the Y dimension twice would cause the diamond to remain the same width be be only half as tall.


It's not manhattan distance because it's being multiplied.


I'm doing just a bit of research on time comparisons, though. I'll get back in a second.

[Rafal99]

Well I never remember which is named Manhattan, square or diamond.

Anyway xdist+ydist+zdist gives diamond.
maximum(xdist, ydist, zfist) gives square.
xdist = abs(target_x - source_x), same for others.

Euclidean distance doesn't require sqrt as I said before, so it will probably be faster than calculating both above distances at the same time. And more accurate.

[madk]

Ah, wait, I made a mistake. Manhattan is indeed a diamond. I don't know how I got the idea that it was a square. My apologies.

[zwei]

Hint: you do not need to have accurate distance, you just need "yardstick" and as such, you can easily just use:

(x1-x2)^2+(y1-y2)^2+(z1-z2)^2

Yes, all distances you are going to compare will be power of two of real distance, but that is not something you have to care about really much if you are looking for closest object without doing pathing.

It can cause probles with displaying rock that is 2 tiles away as 4 tiles away, but you can sqrt it for display purproses (which is done in menus that pause game and as such will cause not slowdown because it is like 10 roots, costing nothing when most lag is user input anyway.)

[fanatic]

(x1-x2)^2+(y1-y2)^2+(z1-z2)^2

I may be wrong, but multiplication is very bad performance-wise, compared to sums bitshifts or Abs, it may be O(log n) or something (my computer science classes are far away...) on the number of bits. but hey the others are just one operation. you cant beat that

[Jake]

Something that's worth bearing in mind here is that the game is currently less than one third feature-complete. At this point Toady One's approach seems to be to put most of his effort into getting the content to fit his vision of the game DF is intended to become, only changing code he's already written when absolutely necessary. Systematic streamlining and optimisation will probably take place after we hit v1.0.
This may be frustrating for us in the short term, but it will ultimately bring us the finished product a lot faster.

That being said, there are not a hell of a lot of game forums where a gripe about performance issues would turn into an earnest discussion about a practical suggestion to help the developer solve some of them. Good on the lot of you!

[zwei]

(x1-x2)^2+(y1-y2)^2+(z1-z2)^2

I may be wrong, but multiplication is very bad performance-wise, compared to sums bitshifts or Abs, it may be O(log n) or something (my computer science classes are far away...) on the number of bits. but hey the others are just one operation. you cant beat that

Yes, it has roughly ~10 as much latency as basic instructions, still lightning fast compared to division (and obtaiing square root):
http://www.intel.com/Assets/PDF/manual/248966.pdf

If you want it rough, you can indeed do abs(x1-x2)+abs(y1-y2)+abs(z1-z2) and be done with it (no need to shift here).

[fanatic]

http://www.intel.com/Assets/PDF/manual/248966.pdf

I think i found what could be my next "Donation" .  Print out bind and send. Potentially could benefit much more than what it would cost.

[frightlever]

Systematic streamlining and optimisation will probably take place after we hit v1.0.

By which time we WILL all have quantum computers.

[Rafal99]

Systematic streamlining and optimisation will probably take place after we hit v1.0.

By which time we WILL all have quantum computers.

By that time DF will have so much features that it will run with 5 fps on quantum computers...
We need some serious optimization earlier imho, fortunately pathfinding rewrite is part of the siege improvements so it should come in the more or less nearby future.

[zwei]

Systematic streamlining and optimisation will probably take place after we hit v1.0.

By which time we WILL all have quantum computers.

A bit overshot, but it is certainly gpood point: feature creep continues to decrease fps, but new hardware offsets that.

[Hammurabi]

Something that's worth bearing in mind here is that the game is currently less than one third feature-complete. At this point Toady One's approach seems to be to put most of his effort into getting the content to fit his vision of the game DF is intended to become, only changing code he's already written when absolutely necessary. Systematic streamlining and optimisation will probably take place after we hit v1.0.
This may be frustrating for us in the short term, but it will ultimately bring us the finished product a lot faster.

%   Release Date
21   8/9/2006
22   10/2/2006
23   1/18/2007
27   10/29/2007
28   7/16/2008
31   4/1/2010

Based on a linear trendline, the v1 is projected to be here sometime around 2034.  I think it is amazing what Toady has done.  Lets just be realistic on how long this ambitious design will take to complete.  Putting off optimizations for another 24 years just isn't going to work.