Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 3 4 [5] 6

Author Topic: most vile enemy of all: lag  (Read 6369 times)

Niseg

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #60 on: April 06, 2011, 03:18:54 am »


Well, I can tell you that how you pathfind means little to nothing compared to the graph you use. DF doesn't have a defined graph, so scattered reads over megabytes of memory is the biggest issue with DF's pathfinding.
I used an array which looks like a bit vector and navigation was done by looking at neighbors. The total runtime is irrelevant because JS as a scripting language is slow by definition. the only modification I did to A* was to add a counter for each node the algorithm visited  .  no path always equals worst case in A*.

With modern processors you can waste all the cpu time you want, as long as you don't need a lot of memory to do so. That being said, it only matters if pathfinding is the bottleneck which I don't believe it is.
with a 3GHz processor your processing time per frame at 100FPS is 30MHz . This is a lot but with a high complexity algorithm you can kill any processor . memory scattering of path finding might also effect the FPS drop especially on a long path . This is why path finding optimizations can help a lot  to bring down processor from 100% (DF is an Atom(tm) smasher).

if you want to see how path finding  kills fps just open the "circus" .
If I was to implement pathfinding for a game like DF, I would use a navigational mesh that gets updated as the world is modified.
The problem isn't using the Nav mesh it's maintaining it. I think a room system (node grouping) that might be a little more memory intensive but it can deal with any shape room even embedded rooms (using a bit vector) . You can also use the rooms for vector pathing (O(1))  first and then fix the path when hitting an "wall" or validate it(O(n)) and fix it(short path A*).

That's the problem with the big pathfinding thread - people have to give suggestions that you can teach the computer how to do. People have to remember the computer does not "see the maze" you have to teach it how to look beyond a collection of points.

That's me! I'll c u in the pathfinding thread. c++ is my forte, btw.
Great, we generally have to convert ideas into algorithms. It took me some time to accept path caching is a reasonable idea and it's really easy to do .  :D

Quote from: Jachim
Admittedly breaching the fun definitely demolishes FPS regardless... it went down to like 10 when I did that. >.<
This is a major spoiler warning
Spoiler (click to show/hide)
Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

LoSboccacc

  • Bay Watcher
  • Σὺν Ἀθηνᾷ καὶ χεῖρα κίνει
    • View Profile
Re: most vile enemy of all: lag
« Reply #61 on: April 06, 2011, 03:28:07 am »

I still think that path caching would give a pretty boost at both low implementation cost and with less regression risk.

I'd start with that, before upgrading to navigation mesh and such.


also, I think the problem with the circus is not path finding per se, but the search for the nearest enemy (which is a secondary use of the same A*, which very conveniently could be used for that)
Logged

Niseg

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #62 on: April 06, 2011, 04:50:45 am »

I still think that path caching would give a pretty boost at both low implementation cost and with less regression risk.

Yeah and it's not a very hard thing to implement  . My implementation uses the "kiss method" . A  wp to wp full path cache (my removal is still buged and you have to regenerate it if you remove much like when adding walls) . All you do is place a few waypoint on the above ground map(if you are underground you won't look at those waypoints unless you want to get outside). Add path smoothing (haven't researched it yet). This will reduce the "confusion" in the outside world .  You can also help it deal with obstructions or just regenerate a blocked paths.

and about HFS:
Spoiler (click to show/hide)

In my program I tried an extreme setup that looks like this(this is not a spoiler just folding a huge map)
Spoiler (click to show/hide)

A*(dx2+dy2 heuristic) got to the target with 544 nodes checked .  Using the paths cached in waypoints it looked at 45 nodes.  To put this into perspective if I block the destination  A* goes through all nodes which yields 849 node search. So without a waypoint to guide it A* went through 64.1% of the nodes in the map while using a simple path cache it looked at 5.3% of them.

You should check out the end of pathfinding thread ( i think page 14 or 15) it has a simple explanation about how it works.  A path cache has the same problem with A* if you don't pick your  waypoints well.  Optimal placement is good but also giving a hint like (if you come from west you don't want this wp).
Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

LoSboccacc

  • Bay Watcher
  • Σὺν Ἀθηνᾷ καὶ χεῖρα κίνει
    • View Profile
Re: most vile enemy of all: lag
« Reply #63 on: April 06, 2011, 05:03:39 am »

this is getting extremely off topic, but one more thing in the 'suggestion' area:

it would be nice if dwarves use the nearest stockpile for delivering goods and stockpile with the 'take' command have a cached path between them

that would make setting up mass dumping/melting delivery a breeze. (also I guess wheelbarrows and backpacks for hauling could start with the stockpile from stockpile routes for an easier implementation and better task management)
Logged

Khift

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #64 on: April 06, 2011, 05:59:06 pm »

While it's clear from all our testing that pathfinding is a detriment on FPS and a very significant one in certain situations (sieges, circus visits, etc) it's also clear that it isn't the main cause of the exponentially decreasing FPS issue we have ALL experienced.

Simply put:
- Idle dwarves barely pathfind
- FPS tests with idle dwarves still result in exponential FPS loss
Therefore, pathfinding is not the cause of exponential FPS loss

Don't get me wrong, I'm not arguing that better pathfinding is unimportant, I'm just pointing out that it cannot be the root cause of the FPS issue.
Logged

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: most vile enemy of all: lag
« Reply #65 on: April 06, 2011, 06:32:59 pm »

^^

They act like pathfinding is happening hundreds of time a second or something, and it simply isn't. Even when dealing with the circus, that doesn't prove anything because there is more that is going on than clowns trying to find dwarfs to murder.

It really annoys me and it also kind of insults the intelligence of Toady and the hackers who actually mess with df internals :/
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

kaenneth

  • Bay Watcher
  • Catching fish
    • View Profile
    • Terrible Web Site
Re: most vile enemy of all: lag
« Reply #66 on: April 06, 2011, 06:54:06 pm »

One massive FPS killer I found is having to many pending jobs for too many dwarves

On a 6x6 embark in .18 I've been running at 4-6 FPS, if I designate the entire accessable surface to Gather Plants, with Plant Gathering enabled on 150 of the 200 dwarves, FPS drops below 1.

If plant gathering is enabled on only a couple dwarves, OR I only designate a few plants for gathering at a time, there is little FPS loss.

(pending jobs * dwarves with matching labor) seems to be a major lag inducer, as DF matches up jobs to dwarves; so I now try to have as few labors enabled on each dwarf as reasonable; such as seperating different types of hauling into dedicated labor pools... but that level of managment wouldn't be feasable without Dwarf Therapist.
Logged
Quote from: Karnewarrior
Jeeze. Any time I want to be sigged I may as well just post in this thread.
Quote from: Darvi
That is an application of trigonometry that never occurred to me.
Quote from: PTTG??
I'm getting cake.
Don't tell anyone that you can see their shadows. If they hear you telling anyone, if you let them know that you know of them, they will get you.

Niseg

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #67 on: April 07, 2011, 08:03:35 am »

^^

They act like pathfinding is happening hundreds of time a second or something, and it simply isn't. Even when dealing with the circus, that doesn't prove anything because there is more that is going on than clowns trying to find dwarfs to murder.

It might be cache thrashing though I haven't found real evidence for it.I prabobaly haven't thought  enough about a way to test it.  If A* doesn't have a "sanity check" it will go through every single accessible node until it gives up. Then there is the issue of how you handle path interruption. There is also an issue of how persistent are the clowns in finding a way through the dead end.

It really annoys me and it also kind of insults the intelligence of Toady and the hackers who actually mess with df internals :/
I'm not sure what you mean by "hackers" , but thinking  and freedom of speech is legal in many countries . Each person can contribute suggestions from his/her fields of interest.

If we had some sort of guide it would be easier to concentrate on things that matter.  As far as I understood Toady seem to resist changes that seem complex. If we show him a working model he'll be more motivated to  work on it.  FPS is a major issue because it's unhealthy for a program to run at 100% CPU 100% of the time.

One massive FPS killer I found is having to many pending jobs for too many dwarves

On a 6x6 embark in .18 I've been running at 4-6 FPS, if I designate the entire accessable surface to Gather Plants, with Plant Gathering enabled on 150 of the 200 dwarves, FPS drops below 1.

I'm don't think that looking at the work queue is an issue. even a linear search 2*O(n) on dwarf list and job list do it just fine. when you designate 200 dwarf to find stuff outside you are starting a major pathing and repathing race and even though open area seem easy to navigate A* pushes a lot of nodes on the queue which may cause a slow down( depending on how they are searched).  If each time a dwarf finds an obstacle he/she recalculates the path from scratch your  CPU will take a beating.

Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

LoSboccacc

  • Bay Watcher
  • Σὺν Ἀθηνᾷ καὶ χεῖρα κίνει
    • View Profile
Re: most vile enemy of all: lag
« Reply #68 on: April 07, 2011, 08:23:54 am »

Quote
FPS is a major issue because it's unhealthy for a program to run at 100% CPU 100% of the time.

whaaaat?

Logged

Kogut

  • Bay Watcher
  • Next account: Bulwersator
    • View Profile
Re: most vile enemy of all: lag
« Reply #69 on: April 07, 2011, 08:31:45 am »

Quote
FPS is a major issue because it's unhealthy for a program to run at 100% CPU 100% of the time.

whaaaat?

FPS is a major issue because it's unhealthy for a program to request more than 100% CPU 100% of the time.
Fixed
Logged
The worst bug - 34.11 poll
Tired of going decades without goblin sieges? Try The Fortress Defense Mod
Kogut, the Bugfixes apostle of Bay12forum. Every posts he makes he preaches about the evil of Bugs.

bragos

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #70 on: April 07, 2011, 10:15:17 am »

-snip-

A*(dx2+dy2 heuristic) got to the target with 544 nodes checked .  Using the paths cached in waypoints it looked at 45 nodes.  To put this into perspective if I block the destination  A* goes through all nodes which yields 849 node search. So without a waypoint to guide it A* went through 64.1% of the nodes in the map while using a simple path cache it looked at 5.3% of them.

You should check out the end of pathfinding thread ( i think page 14 or 15) it has a simple explanation about how it works.  A path cache has the same problem with A* if you don't pick your  waypoints well.  Optimal placement is good but also giving a hint like (if you come from west you don't want this wp).

you're using a inadmissable heuristic (which also result in suboptimal paths on your site).
you probably forgot to to the square root (Pythagoras). that would make it admissible.

A heuristic function (for A*) is admissible only when the expected (heuristic) value is always equal or lower then the actual value.
ie. it MUST be an optimistic 'guess'

Logged

zazq

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #71 on: April 07, 2011, 03:00:21 pm »

Hey now, while arguing the usefulness of various pathfinding algorithms may indeed fix lag, what we really need is things that significantly reduce lag right now regardless of why they work.

I can vouch for the big stairwells causing lag, because I built a stairwell free fortress and it ran at 70fps.  I then replaced the walls with up down stairs and it ran at 30fps.  I expect that if you used stairs like ramps then they would be equally lag free (like never using an up/down stair, just having single flights at a time, connected by a short hall. 

Hallways prolly reduce lag.  This is only true if you also put restricted traffic areas on all the doors.  This has something to do with pathing magic, but it works so we don't need to know why.

Clothing?  Everyone's talking about modding the game so dwarves don't wear clothing.  I think this is a great idea, is there a how-to?

low animal populations help reduce lag.  Half the animals starve if you don't take care of em, which is fine by me.  The few that are carnivorous (nonivorous?)  you can get rid of by having a surprise danger room in the middle of the hallway.  unarmored dwarves tend to survive unhurt, and babies and pets get axed.  Bees are ok because they vermin teleport instead of path, but ducks are not ok.

use dfcleanmap.  use it always.  if it cleaned the dwarves themselves that would be even better, but there's no non-water way of doing that.

what else?  The wiki has a long list but most of them just don't do anything.
Logged

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: most vile enemy of all: lag
« Reply #72 on: April 07, 2011, 03:32:27 pm »

It really annoys me and it also kind of insults the intelligence of Toady and the hackers who actually mess with df internals :/
I'm not sure what you mean by "hackers" , but thinking  and freedom of speech is legal in many countries . Each person can contribute suggestions from his/her fields of interest.

If we had some sort of guide it would be easier to concentrate on things that matter.  As far as I understood Toady seem to resist changes that seem complex. If we show him a working model he'll be more motivated to  work on it.  FPS is a major issue because it's unhealthy for a program to run at 100% CPU 100% of the time.

Toady isn't resistant to change. People have demonstrated significant causes of slowdowns in the past, and those issues have been fixed. What you're doing is going up to a professional race car driver and telling him to put a bigger exhaust on his engine to make his car go faster.

DF has a working model already for pathfinding, and it gets the job done. You would need to demonstrate how your ideas would improve over the model that you know nothing about AND prove that the performance increase is worthwhile. The fact that DF is closed source doesn't mean anything to the hackers. To us the binary is just as good as source code and we have no trouble understanding it or modifying it for our needs.

For example, there is a function that runs every frame and checks to see if you have designated anything on the map (like digging). Map blocks in the game are 16x16 with a 16x16 array just for designations. The game doesn't scan through every block to see if you designated it or not, each map block has a dirty bit it checks instead. By removing the dirty bit and using a dirty list instead can eliminate hundreds of branches per frame and make that segment of code run orders of magnitude faster. The question is, will this change matter on a fort that is getting 20 fps? The answer is no.

DF preforms well enough and modern processors are amazing. When people are getting exponential slow downs on a fort, it isn't something that will be solved with a minor speed boost to a single function.  They are most likely experiencing a bug. Just do the math, for a pathfinding fix to take a 20 fps fort to 100 fps would require your pathfinding code to run in negative amounts of time and violate the laws of physics. While my own life means little to me, there are people on this planet I care about and they would be snuffed out in an instant as the world was destroyed which forces me to take a stance against such a thing.

The best thing to do is generate forts on .25, use seasonal saves, and if you encounter a massive slowdown for no reason all of a sudden upload a before and after save to DFFD to let Toady and the hackers look at it. I personally haven't ran into the problem with a .25 generated fort, but I haven't had enough time to really play as much as I would like.
« Last Edit: April 07, 2011, 03:44:20 pm by devek »
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

LoSboccacc

  • Bay Watcher
  • Σὺν Ἀθηνᾷ καὶ χεῖρα κίνει
    • View Profile
Re: most vile enemy of all: lag
« Reply #73 on: April 07, 2011, 03:40:18 pm »

clothes: just substituting the soft tag with hard helped my fort a lot without introducing side effects due to greater chance of contact disease

animals: browser will die, cat are slower to adopt now and butchered on sight - other animals tend to move more or less randomly or on shorter paths (from the animal to the owner).
turkeys are quite good balanced bones and food source: have a food stockpile to remove eggs from nest and you're ok. just forbid a couple now and then to keep a breeding pair or when you need that meat reserve

embark area: 3x3 is a good balance between minerals and lag. 4x4 is nice for megaproject but has a too much large surface area to search paths* and 2x2 is super fast but you'll found yourself on shortage of metals eventually

*path is basically hit or miss depending on your layout. an example of bad layout is having magma smelters down below at the magma sea and bedroom/meeting halls at the first underground rock layer.

that means: for each level of down stair that get analyzed for path cost a circle of tiles on the surface gets checked. and as the circle expands, more and more tiles have to be checked for a single down evel of stairs. that happens also on ramps and such.

having two workforce burrowed and up and down and a  handful of haulers will help a lot. but as other says, unless you have a really bad layout (a central 3x3 stairwell) and a huge number of creatures and sieges or ambush pathfinding is not the single main culprit.

Logged

Juason

  • Bay Watcher
    • View Profile
Re: most vile enemy of all: lag
« Reply #74 on: April 07, 2011, 10:44:54 pm »

I have always played with a central 3x3 stairwell, and can't say I have unusually bad lag.  My i7 820QM laptop gets over 100fps with 105 dwarves on a 4x4 map with temp/weather off.  I'm down past the first cavern, with about 20 Z-levels explored, and 50 animals in large pastures.  That "seems" fast to me, but maybe I'm missing something :P

What testing was done to come to the conclusion that a single central stairwell like that would cause problems?

Logged
Pages: 1 ... 3 4 [5] 6