Bay 12 Games Forum

Please login or register.

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

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

Draco18s

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

Well, the idea above is that you're never really using the whole map.  What you're using instead is a composite of all of the separate contiguous chunks (effectively--you have an active set, and an inactive set).  Each path call only path finds in its chunk (obviously a destination that is outside of the chunk's data range doesn't even need to try, it just returns a failure).

Ideally, you only store any contiguous region that has creatures in it, though separating out what does and what does not may be a non-trivial problem.

Also, you would have to garbage collect old chunks that haven't been used in "a while" as to keep down the memory footprint (mind, we are attempting to trade CPU for memory here, but there is no sense in using more than we have to).  Another non-trivial problem would be finding the "the stupid dorf locked himself in" single-tile chunks and delete them when the dwarf is let out (eg, a wall was built on that particular tile and that area will never be an active set*).  If not, it will eventually fall out of the inactive set.

*This here might be a part of a larger issue: do you update the inactive chunks as walls are built?  Likely would be trivial in both the programatic sense as well as the computational sense.  Just update all chunks with the new wall (each chunk that does not have that location inside it does nothing).  If it splits a region, don't worry about it.  Assuming a chunk is divided by new walls (making two smaller chunks) don't worry about it, you can worry about splitting it when it becomes active again later--assuming it ever does.
Logged

DeathOfRats

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

@Puzzlemaker: True. That's why I mentioned I wasn't sure how tricky dividing a given concave shape into convex shapes was. Actually, I just thought of a shape that is very tricky: a ring. It's clearly concave, and dividing it into any kind of convex shapes is a pain in the rear.

I still think that some sort of node-based pathfinding is, in general, a better bet than tile-based, though. Actually, I'd say that tile-based is just a degenerate case of node-based, in which eat tile has a node. Also, reusing previously calculated paths (always a good idea) would be much easier with nodes than with tiles.

@Draco18s: I think I see more or less what you mean, but,  I'm not 100% sure how it'd work. How do you path from a location with a dorf to one, say, on the other side of the map (which would, presumably, be in none of the chunks you've stored)? Would that cause the system to suddenly store a good portion of the map in memory?
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #17 on: October 13, 2009, 07:47:34 am »

@Draco18s: I think I see more or less what you mean, but,  I'm not 100% sure how it'd work. How do you path from a location with a dorf to one, say, on the other side of the map (which would, presumably, be in none of the chunks you've stored)? Would that cause the system to suddenly store a good portion of the map in memory?

2 things:

1) non-trivial to decide that a chunk is never used (eg. no creatures in it, no path to anything else), but could be possible for smaller chunks.
2) if it's a chunk there are no paths to any other chunks, which is what makes it a chunk.  Thefore, attempting a path outside of the chunk, (as previously stated) fails.

As for deciding which chunks are active and inactive, my gut reaction would be to use the connectivity map (the floodfill).  Each portion of the map that is one "color" in the floodfill is its own chunk.  Hopefully not every time the floodfill is updated do we need to make new chunks (because a wall was built, a tile was mined, etc), as we could hopefully isolate which tile changed status (from walkable to not, and vice versa) and just update that one tile on all chunks (active and inactive).  The only reason to make  new chunks or to swap out chunks would be if doors, floodgates, bridges, or other such structures changed status.  Then isolate which chunks are effected and move them to the inactive set and find smaller inactive chunks which have already been computed that make up the lopped off sections (then perform a new chunk creation for any remaining empty areas).
Logged

smjjames

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #18 on: October 13, 2009, 08:43:41 am »

Maybe you guys could solve the animal pathfinding issue vs animal forbidden doors? Unless more than the pathfinding code is involved.
Logged

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #19 on: October 13, 2009, 08:46:17 am »

Ah, I see I was misunderstanding what you meant for chunks.

I would imagine updating new tiles in one chunk or the other not to be too difficult, as long as the chunks retain location information. Besides, technically you'd only need to consider active chunks (I cannot really think of a case in which an inactive chunk would need to be updated - or why it can't be done at activation time, for that matter).

My main problem with that is that you're going to end up with at least one giant chunk (i.e., the great outdoors), more if you do something silly like mine out a whole level underground (by contrast, that whole level could well be a single node in a graph, saving lots of memory and processing time unless you're pathing inside that particular level). Pathing within those chunks would still be a pretty big problem.

Still, I like the idea of only considering for pathing those areas that can be reached by dorfs (though I'd prefer to be able to include things like flying/swimming creatures, pets and building destroyers, not sure how we could handle that easily), and considering areas without possible connections as separate areas (at least, that would reduce lag from pets and other critters trying to path through closed doors).
Logged

zwei

  • Bay Watcher
  • [ECHO][MENDING]
    • View Profile
    • Fate of Heroes
Re: Anouncing The PathFinder Project
« Reply #20 on: October 13, 2009, 09:15:14 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.

You can easily solve this by applying computer vision segmentation algorithms. Efficient ones have only two passes (one over image data, one to complete shapes.). That is 2d of course, but extending algorithm to 3d is trivial and retains same properties (two o(n) passes) and commonly used in medical applications to analyze MRI data.

DeathOfRats

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #21 on: October 13, 2009, 09:24:18 am »

I though about using your typical two pass connected components algo, but you don't really want to have to do the whole thing again at every frame (even if it's not prohibitive), and the algo has to be able to merge and un-merge zones easily: depending on your criteria for a room, if it's "Continuous area" you'll be having a single really big zone, if it's "Convex area", a convex area can turn into two with the addition of a single wall tile, and viceversa. Neither of those may be ideal, depending on how the pathing algorithm works.
Logged

Slogo

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

There's definitely going to need to be a hierarchy to it all (chunks, nodes, whatever you want to call them). It helps immensely with the pathfinding because it distributes the work over several different points rather than needing to know a full tile per tile path right away.
It helps with caching the popular routes too as you can cache the routes that connect one region to another.

Fieari

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #23 on: October 13, 2009, 11:59:40 am »

I don't have immediate time to contribute to the coding, but here's an old thread I posted about my thoughts on making multiple movement types possible: http://www.bay12games.com/forum/index.php?topic=33667.0
Logged

Silverionmox

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #24 on: October 13, 2009, 01:01:38 pm »

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.
We should piggyback on the player's efforts there. He uses room definitions, burrows and zones, and we should make good use of that. As soon as workshops are defined similarly to bedrooms etc., much of the interior of a fortress will have been defined as rooms - and that's where most of the pathfinding happens. When the military arc gets some more attention, there probably will be first line of defense zones, second line of defense zones etc. that the player can define as part of his fortress strategy, to give orders more easily. Those can be used as well.
Logged
Dwarf Fortress cured my savescumming.

Fieari

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #25 on: October 13, 2009, 01:07:23 pm »

Zones are less likely to have chokepoint access though.  Rooms are usually set to have doors as their only way in/out.
Logged

Slogo

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #26 on: October 13, 2009, 01:44:53 pm »

There's no need for the divisions to be defined along any sort of human friendly mechanism. It's about what the computer can handle the best.

Silverionmox

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #27 on: October 13, 2009, 02:32:31 pm »

There's no need for the divisions to be defined along any sort of human friendly mechanism. It's about what the computer can handle the best.
If we're using divisions, we might as well use the existing divisions that are supplied ready-made by the player. Those automatically are in the areas where the player wants stuff to happen and pays attention to. If we save on calculations at the cost of reduced accuracy, nobody cares if something in the wilderness doesn't go in a straight line to its goal. Inside of a fortress, that might be annoying if it happens systematically.
Logged
Dwarf Fortress cured my savescumming.

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #28 on: October 13, 2009, 02:49:13 pm »

Draco18s:  I don't think its viable to have the pathfinding engine keep tabs on ware active creatures are or are not.  That's client data and the client will be what spawns/destroys the creature and it could do them any ware it pleases.  All the pathing engine needs to worry about is if it receiving path requests that have said area as an end point.  If indeed it's never getting requests their then it could skimp on its representational model of that area in some way, though I'm not sure how best to do that.

DeathofRats:  Concave/Convex sounds much too difficult, I favor a system of all rectangles as described in this thread

http://www.bay12games.com/forum/index.php?topic=42678.0

Not only are rectangles the most common thing people build in DF their also efficient at covering the unmodified terrain as well and are much simpler to set up and can aid in doing multi-tile creatures as we can be assured that a creature thats longest dimention is shorter then the rects shortest can move through the rectangle.

Silverionmox:  I'd be careful with using such data as DF allows zones to be chopped up and built over to the point that they would be useless for pathfinding, and as were already going to need a system that creates nodes without such cues I don't see much advantage using the data.  Though here might be something to be gained in being able to request a path at the level of a node which is known to be contiguous with a destination.

I've though a bit more about the Tree structure I described earlier and think it could do quite a lot.  Paths could be found by a kind of tree traversal rather then by a traditional method like A*.  Think of it as progressively slicing away everything that is not a path from an area know to contain both end points.

To start with the leaf nodes will have connections (edges) amongst each other.  These edges determine the next node up the tree as the rule is that all the daughter nodes of a node are connected.  The connections amongst the daughter nodes of a node constitute the "INTRA" connections of the node and when they change the membership of the daughter nodes needs to be checked to see if they still connect.  Any connection by a daughter node to a non daughter node is an "INTER" connection.  Inter-connections between the daughter nodes of two nodes will result in an Intra-connection between the parents, when they change the Intra-connection of the parents is updated.  The Inter-connections at each level of the tree cause Intra-connections on the next level up.  All connection changes propagate up the tree until the tree is accurate again.

To path through the tree the two leaf nodes containing the endpoints are identified and an upward propagating check is made for a matching parent node is made.  If a common 'ancestor' node can be identified below the root node then it means theirs a path and the path must exist within the set of tiles described by that ancestor node.  Now starting with common ancestor the tree is descended in successive steps.  In each step a group of nodes is searched for a path at Inter-node levels between two nodes known to contain the end points.  The resulting set of nodes on the path are then opened and their non-leaf daughter nodes become the search set the next step until all nodes on the path are leaf nodes.  Because each search level is through a small number of possible nodes it will be far faster to do a dozen searches through networks of only a dozen nodes each then to search the leaf level nodes directly.
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

Idles

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #29 on: October 13, 2009, 03:21:22 pm »

To path through the tree the two leaf nodes containing the endpoints are identified and an upward propagating check is made for a matching parent node is made.  If a common 'ancestor' node can be identified below the root node then it means theirs a path and the path must exist within the set of tiles described by that ancestor node.  Now starting with common ancestor the tree is descended in successive steps.  In each step a group of nodes is searched for a path at Inter-node levels between two nodes known to contain the end points.  The resulting set of nodes on the path are then opened and their non-leaf daughter nodes become the search set the next step until all nodes on the path are leaf nodes.  Because each search level is through a small number of possible nodes it will be far faster to do a dozen searches through networks of only a dozen nodes each then to search the leaf level nodes directly.

So what are you going to use as leaf nodes? Obviously not DF tiles, or you'd be duplicating much of the data inherent in DF's internal tile representation. Are your dynamic rectangles == leaf nodes? If you use dynamic rectangular grouping of tiles, rather than a uniform grid of tile "chunks", you then have to keep track of the spatial location of each rectangle, so that it can ultimately be mapped to DF tiles. This system does, however, allow you to optimize for areas in which pathing is homogeneous, such as large open expanses of sky.

Also, remember that a search performed on our path node hierarchy must return a valid path if a valid path exists within the current pathing engine, so we must be careful when optimizing the connections in the path tree. It is not as important, however, if our computed path is sub-optimal (longer) than the current best-path method.
Logged
Pages: 1 [2] 3 4 ... 43