Print

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

[Xzalander]

Also a lot of the work could probably be offloaded to any second CPU of the computer, bringing instant relief to many.

[/quote]

God yes. Im on a quad core Hyperthreaded pc (4phys 8virtual) and DF only uses one of the potential 4 real cores. The graphic card is picking up (or is able to) the video requirements... so come on Im sure a lot of us have atleast 1 other core, some of us up to three more just going idle.

[jei]

(computer) memory usage wise this would be a non starter right now.  storing every path, for every dwarf, would be impossible.  also this has the disadvantage of being non reactive to changes in the map.  if you use the rectangle approach described in the post above, you could store some common subpaths, and have those be exchanged in conversation though.  i totally see some dwarves taking the 'long' route, while the lazy good for nothing dwarves that party all the time taking the most direct route everywhere.  dont see how this adds to gameplay.  it would make the game more FUN though, as your busiest dwarves still take dumb paths during seiges that lead to their slaughter.

the old crappy paths would essentially be mental diseases that spread infecting younger dwarves, making them walk obtuse paths.

I think you would soon find out that most people don't consider the dwarves doing random things as FUN, as opposed to them doing what you would assume and consider logical and intelligent. (Such as masons frequently building themselves inside the walls.) People sort of presume some basic intellect and logic to be there. Moody dorfs can still go wander around and commit suicides and be logical about it without suffering from algorithmically induced insanity.

Also dorfs learning paths and exchanging them in conversations sounds like "yet another nice but useless feature eating memory and CPU." And we have plenty of those already.

[zilpin]

The original post sounds a little bit like D*

Sure, it would be great.

D* is pretty good at avoiding "mental disease" paths that the later posts worry about.

But replacing the pathfinding algorithm is non-trivial.  Enormous amount of code, boatloads of new bugs, and no new functionality or features.
Maybe if Toady could offload that work to a team it would be feasible.

[smariot]

The original post sounds a little bit like D*

Fixed the link, but I don't think this sounds like D*. The dwarves definitely know the terrain between them and the booze stockpile, there's no unknowns for them to try to (un)intelligently work around.

[zilpin]

Sorry for bad link.  Thanks for fixing.

'Unknowns' can also mean changes to the map structure.  Like, for example, doors opening and closing via lever.  Or the amount of crowding in a hallway.
The D* algorithm is good at recalculating only a portion of the path, rather than performing an entire new pathing solution, and then also re-using that new path among other entities which use the same rules and are impacted by the same event.

My understanding of the current pathing code is that nearly every step for every entity recalculates their entire path, with some case-specific optimizations implemented for water, animals, and other situations.

D* can give an A to Z path, then the dwarf uses it until they reach an obstacle, only re-pathing when an obstacle is met.  And the path can be re-used by other dwarves for as long as it works, then updated by the algorithm when any dwarf has a problem.

That's what makes D* nice for maps with 'unknowns', as well as changing topography.

[ZCM]

It's really hard to give suggestions without knowing what DF's current pathfinding code is doing. A few observations though.

* Too much work is being done finding really long paths. No matter how much work you do to speed up pathfinding, a really long path is always going to be more work. Moving to the wrong side of a block to mine, going to the staircase to get a stone 1 z-level down rather than one 3 tiles away on the same level ... those things eat up CPU.
* Too many things are using pathfinding. Why are animals using the pathfinding code? A routine that tries to move towards something the animal sees and gives up if it's blocked is not only faster, it's usually more realistic. (Make an exception for trained animals.)
* Some variant of the A* algorithm is probably best, but A* reacts badly to situations that are natural in multi-Z-level pathfinding, things like this:

########################################
#......................................*
#.######################################
#..@....................................
########################################

* Setting the default pathing cost at higher than 1 kills the performance of A* when the best path is close to a straight line. Seriously. But due to the multi-Z-level problem you probably won't notice.
* Nobody cares if your pathfinding gets the absolute shortest path, as long as it's not dramatically wrong.
* A* can be modified to find a path to the closest one of many things. This is often faster than first choosing an item then pathing to it.

[devek]

What are your opinions of building a hash mesh?

http://www.ai-blog.net/archives/000152.html

If done right, it wouldn't be hard to modify the mesh when a door is closed or you build. I could optimize around some of multi-z levels by building a flat mesh in outdoor areas or anywhere that isn't a connected level above or below.

[thijser]

Another important question is should annimals have the same pathfinding? It might work better if we only let annimals path to object they can see and therefor will have a pretty straight forward path.

[ZCM]

What are your opinions of building a hash mesh?

http://www.ai-blog.net/archives/000152.html

Totally irrelevant - waypoints vs meshes is a problem for games that have arbitrary geometry. When your game is based on a fixed grid it's a mesh by default. Also, that article is complaining that games are valuing speed over correctness, and should use more correct but slower algorithms, which is exactly the opposite of the problem DF has.

[devek]

I know what the article was talking about, but what I meant is like...

Keeping a geometry based view of the world and pathfinding through that, instead of the current unspecified graph. A r tree without overlap shouldn't perform that badly when you consider how much less memory is used when searching.

[jei]

I think optimizing the path finder any further is probably more difficult and demanding task than simply offloading the "find a path" -task to a separate thread or a second CPU.

[ZCM]

I know what the article was talking about, but what I meant is like...

Keeping a geometry based view of the world and pathfinding through that, instead of the current unspecified graph. A r tree without overlap shouldn't perform that badly when you consider how much less memory is used when searching.

Don't bother trying to speed up individual node lookups; to do faster pathfinding you need to reduce the number of nodes, or the number of searches. The dominant cost in A* in my experience is juggling the priority queue.

There are algorithms to do pathfinding on higher-level graphs which might help. Unfortunately they're complicated and require updating part of the high-level graph every time part of the world changes, which is expensive.

[Xzalander]

Another important question is should annimals have the same pathfinding? It might work better if we only let annimals path to object they can see and therefor will have a pretty straight forward path.

This should hold true.. add another tag like [MEMORY], which basically implies any intelligent beings use the full A* pathing system, anything which doesnt uses a Line of Sight A* system.

(Implying that [memory] is just a loose term for "I can pathe because I (loosely) remember what was where". Sure animals have "memories" too but in this instance it would make it easier on the pathfinding and being a taggable entry those who wish can have [Memory] Animals...)