Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: [1] 2 3 ... 43

Author Topic: Anouncing The PathFinder Project  (Read 96287 times)

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Anouncing The PathFinder Project
« on: October 12, 2009, 08:06:55 pm »

Many of you may already be familiar with the Khazad project, its an effort to explore the best possible UI for Dwarf Fortress, along the way we had our first spin off project dfhack lead by Peterix.  It was an outgrowth of the map reading code I'd initially obtained from Sinoth's 3Dwarf project and which was heavily upgraded by Peterix.  We felt it would be a great boon too other programmers to have its core map reading functions available as a library and indeed it's been getting used for just that.  I'm now pleased to announce the start of another side project of Khazad, the PathFinder Project.

As you all know Path finding is by far the biggest drag on DF's FPS and the main limiter of Fortress size, indeed the current #4 suggestion on Eternal Suggestions is "Speed Up Pathfinder".  Many programmers have suggested  ways to improve the speed of these path searches or ways to over-come certain limitation inherent in the current implementation.  If a solid system can be demonstrated we hope it will be incorporated into DF, to this end the library will use the BSD license.

I've invited a number of programmers and designers together to work on this task.  Our initial team is already large but more are welcome to join (to compensate for those individual unfortunate enough to be hit-by-a-bus)

Puzzlemaker (lead)
Slogo
Draco18s
Silverionmox
Sunken
numerobis


And what project would be complete without a mission statement:

Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.

The idea here is that the library will be very modular and easy to include into a game, acting almost like a server in which it receives an initial dump of map data from the client, and then during game play the client sends map updates on changes and path requests and the server sends back the needed paths.


Khazad & dfHack would provide a platform for testing, viewing and measuring how effective it is (by use of a path request generator) and allow the programmers to concentrate on pure path finding without worrying about anything else.  The first task is to of course do a bunch of design work some of which will take place here, everyone is free to help out on that but please do keep things on topic.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Puzzlemaker

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #1 on: October 12, 2009, 08:13:31 pm »

This is going to be fun.  Yay!
Logged
The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.

Alexhans

  • Bay Watcher
  • This is toodamn shortto write something meaningful
    • View Profile
    • Osteopatia y Neurotonia
Re: Anouncing The PathFinder Project
« Reply #2 on: October 12, 2009, 08:21:45 pm »

Posting to keep track of this.  I think I'm gonna learn some interesting things...  ;)
Logged
“Eight years was awesome and I was famous and I was powerful" - George W. Bush.

Idles

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #3 on: October 12, 2009, 09:34:13 pm »

Here is a very, very helpful resource that outlines a pathfinding system:

http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/

I was planning to implement his system in a personal project, but alas this semester has a heavy workload. He has done performance analysis on his implementation of the system, and shows it to be much more efficient than straight up A* for long path-lengths. One of the big elements this paper does not cover is the method of updating the pathfinding graph based on changes to the game world, but it looks like a relatively easy problem to solve. The code also does not address extending this 2D system to 3D, but that problem is also not terribly difficult to solve.

The system handles hierarchical pathfinding (finding paths at a high level and low level), multi-tile creatures, and multiple travel domains (walking, swimming, amphibious, flying, etc.). Connected components checking (currently used by DF) can be done relatively quickly by inserting the path start and end nodes into the abstract graph and finding an abstract path between them. This new form of CC checking would even work for flying monsters, unlike the current code!

Definitely worth a read as a starting point for designing the system.
Logged

buman

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #4 on: October 12, 2009, 11:44:15 pm »

Quote
acting almost like a server in which it receives an initial dump of map data from the client,

This would allow it to be coded as a parallel thread yes?
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #5 on: October 13, 2009, 12:55:34 am »

Possibly, though I don't have enough experience with multi-threading to know the benefits or difficulties of doing so.  If some of the team members know how to do it then it could be something they establish as a goal.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

zwei

  • Bay Watcher
  • [ECHO][MENDING]
    • View Profile
    • Fate of Heroes
Re: Anouncing The PathFinder Project
« Reply #6 on: October 13, 2009, 01:58:49 am »

Major challenge you will face are disconnected / reconnected world areas and 'soft' changes.

Simple drawbridge raise or door lock can disconnect and reconnect large parts of world, leading to potentially huge overhead and path recalculations with no benefit, if you are to deliver real improvement, you will need to be able to store several versions of already pathed map cached to avoid pointless recalculations for expected, but random, changes.

Also, since you know how map will look like in n+ seconds (cue taken from dig/build/cut tree designations and dwarf locations), you can have pathed maps (or sections of pathed map) ready to be instantly plugged in when construction/designation is being excecuted and when it is finished.

You can also, for example, precalculate map for next season because you know that tree saplings will become obstacles.

If you work with prediction in separate thread, you can have already updated map when game commints changes and really requests path.

I think you are looking for more df-connected system than you would expect.

---

Also, I hope you did consider batching map changes and not commiting them and recalculation pathing before actual path is requested: Often, several changes can happen at same time.

Angellus

  • Guest
Re: Anouncing The PathFinder Project
« Reply #7 on: October 13, 2009, 02:10:48 am »

Major challenge you will face are disconnected / reconnected world areas and 'soft' changes.

Simple drawbridge raise or door lock can disconnect and reconnect large parts of world, leading to potentially huge overhead and path recalculations with no benefit, if you are to deliver real improvement, you will need to be able to store several versions of already pathed map cached to avoid pointless recalculations for expected, but random, changes.

Also, since you know how map will look like in n+ seconds (cue taken from dig/build/cut tree designations and dwarf locations), you can have pathed maps (or sections of pathed map) ready to be instantly plugged in when construction/designation is being excecuted and when it is finished.

You can also, for example, precalculate map for next season because you know that tree saplings will become obstacles.

If you work with prediction in separate thread, you can have already updated map when game commints changes and really requests path.

I think you are looking for more df-connected system than you would expect.

---

Also, I hope you did consider batching map changes and not commiting them and recalculation pathing before actual path is requested: Often, several changes can happen at same time.
What he said, the smartest move probably is to let the 'server' constantly run to calculate different map possibilities and store them. Maybe even try and program the pathfinder to change the blocked parts? (If bridge is in way, then take route 16)
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #8 on: October 13, 2009, 04:12:02 am »

Quote
What he said, the smartest move probably is to let the 'server' constantly run to calculate different map possibilities and store them. Maybe even try and program the pathfinder to change the blocked parts? (If bridge is in way, then take route 16)

Constantly creating random paths and caching them sounds like a very wasteful approach, not only would their be very very little likelihood that those random paths would match the actually needed ones but it would eat up cpu cycles constantly (I'm not going to assume multi-threading at this point).  I think any kind of useful caching system will be one that caches only paths that have actually been requested by the client AND keep getting requested frequently.  Of course their would be a means to adjust cache size and the 'stinginess' of the cache/don't cache logic would respond appropriately.

Quote
Also, I hope you did consider batching map changes and not commiting them and recalculation pathing before actual path is requested: Often, several changes can happen at same time.

This is an interesting idea that should be explored.  Were defiantly going to need a system that can receive map changes in groups of tiles (such as the raising of a draw-bridge which affects dozens of tiles simultaneously) so it would seem that saving certain connectivity calculations until a path is requested might indeed save a lot of recalculating.

The high level connectivity zone issue (such as when the only drawbridge over the chasm that divides the whole map in two is raised and we need to know that their are no possible path across) can be solved with a Hierarchical node system like that in the links provided by Idles.  Most such systems use only one 'layer' of abstraction above the actual map data but I see no reason not to use many in a tree structure.  The leaf nodes would consist of groups of connected tiles and each subsequent node moving towards the root would be a larger and larger interconnected group of nodes, the final set of nodes directly connected to the root would constitute the fully disconnected regions of the map and it would be a simple matter to check if that node matches for any two tiles.

The tree would of course need to be changed to reflect changes in the map but this would be relatively simple because an area that detaches from the rest of the map can just be 'grafted' onto the root and then grafted back when they reconnect.  That keeps the modification to the tree as small as possible.  I'd need to think further on how some of the other systems like movement domains would work, it might makes sense for them to each have a separate tree or to have separate nodes in the same tree or even shared nodes, though I suspect separate trees are the best solution.
« Last Edit: October 13, 2009, 04:14:01 am by Impaler[WrG] »
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

DaveT

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #9 on: October 13, 2009, 04:25:25 am »

More fun: Entirely different implementation of pathfinding where entities don't have complete knowledge of land that they haven't seen. Based around the principle of forgetfulness of dorfs, they remember where they have been for a certain amount of time based around the number of times they have been there and the length of time since they were last there.

Bonus points if every time a group of male dorfs get together at a party they discuss routes and improve on their knowledge of surrounding terrain.

90% lighthearted. 10% because I'm going to implement something like that for a pseudo game that I'm 'developing' (as in I want to be but get very little time to spend on it).
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #10 on: October 13, 2009, 04:39:10 am »

One other though, the library will need to have a huristic function in which it returns (very very promptly) a reasonably accurate estimate of a paths length without actually going through all the trouble of producing the full path.

Getting this right will be key because a game like DF is making huge numbers of checks for potential paths for every one that is actually conducted.  I'd say its so important that design should be centered on optimizing this huristic function even to the detriment of full path creation.  Some control over the amount of uncertainty in the huristic would also be nice, say either as an accompanying argument on each request or as a setting at initialization.  This would allow the client to trade off time and accuracy to for example test a large number of possible paths with low accuracy and then test the three best with higher accuracy for to make a final decision.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Firnagzen

  • Bay Watcher
  • [CURIOUSBEAST_INSANE]
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #11 on: October 13, 2009, 04:45:46 am »

Hmmm. One thought/wish: Could you do something about the pathing of fliers, so that they actually use it?
Logged
Christ, are you dwarves or are you elves? If you think Hell has too many demons, then you kill them till the population reaches an acceptable number.

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #12 on: October 13, 2009, 06:38:19 am »

Major challenge you will face are disconnected / reconnected world areas and 'soft' changes.

The way to do this might be to store chunks of the map that become disconnected as the result of a path change (update as needed).

Eg:

Whole map (stored)
#######^###### <-- path to more map
#.............#
#######*######  <-- door
##..........##
##############

When the door closes, you store this

##############
##..........##
##############

As a separate chunk that shows the paths only in that portion of the map, and assumes that it is disconnected from the rest.  When the door opens again, you go "ok, not using it, but I'm not throwing it away" and save it for later when the door gets locked again.
« Last Edit: October 13, 2009, 07:18:49 am by Draco18s »
Logged

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #13 on: October 13, 2009, 06:54:29 am »

You don't really need to store the whole thing. Instead, what you can do is define it as a room (where room = convex shape - not sure if the division of a complex shape into convex areas is a tricky prospect) and generate a graph of rooms and their connections. Then, when a door is closed, or a floodgate raised, or whatever, you just remove the connection between the rooms (or maybe just tag it as unavailable. Having multiple possible tags - impassable, passable for swimmers, passable for fliers, passable - would also allow for different tagging based on movement type). Pathing would be done in a per-room basis, with in-room pathing having its own very simple algorithm (could even be just "Move one square in the direction of the destination". Since the room is convex, you're guaranteed to reach it that way).

Of course, something like that is not really suitable for great expanses of open space, but rather for areas where you have lots of small rooms, and it would still require some sort of algorithm to do the pathing, since it's just a data representation.
Logged

Puzzlemaker

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #14 on: October 13, 2009, 07:27:02 am »

A major problem with that room idea is dynamically defining the rooms.  The players can create very strange shapes, which may be hard to keep track of using any algorithm.
Logged
The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
Pages: [1] 2 3 ... 43