Bay 12 Games Forum

Please login or register.

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

Author Topic: Burrows and pathfinding  (Read 4492 times)

Draco18s

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #15 on: July 06, 2009, 04:29:01 pm »

What I want to know is what's been considered (or already implemented!) in terms of intelligent segmentation of space into larger units.

Here's a thought.  Cache basic routes between each burrow.  That is, assume each burrow is a contiguous area (that is, assume that a floodfill limited to the burrow will fill the whole thing, excepting walls).  Then calculate paths from each burrow to each other burrow.  Use a rough center calculation on which square to start from, the start square must always be in that burrow, of course, such that a torus shaped burrow doesn't calculate from the doughnut hole.
Logged

Fieari

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #16 on: July 06, 2009, 07:52:49 pm »

What is currently implemented is that everytime there's a change to the walkability of a tile (mining, building walls, locking doors, flows running across the map, etc), the game seperates the entire map into connected regions using the floodfill technique.  Each map tile is assigned a single number... I forget how many bits is allocated to it but IIRC it's not a huge number of them... and then when a creature wants to pathfind, it compares the number of it's current tile to the number of it's destination, and if they are the same, runs A*.  At that point, the route the creature is taking is saved, and the dwarf follows that path.  If the path changes and the creature runs into an obstacle, the path is recalculated with A* again (but only when the dwarf actually hits the obstruction).

That's it.  That's the pathfinding system right now.
Logged

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #17 on: July 07, 2009, 01:17:12 pm »

Here's a thought.  Cache basic routes between each burrow.  That is, assume each burrow is a contiguous area (that is, assume that a floodfill limited to the burrow will fill the whole thing, excepting walls).  Then calculate paths from each burrow to each other burrow.  Use a rough center calculation on which square to start from, the start square must always be in that burrow, of course, such that a torus shaped burrow doesn't calculate from the doughnut hole.
"Then calculate paths from each burrow to each other burrow" can be arbitrarily inefficient. The best path from A in burrow 1 to B in burrow 2 might be idiotic for getting from C in 1 to D in 2 - provided that two burrows have more than a single overlapping tile.

That's it.  That's the pathfinding system right now.
That's what I thought. These connected components are potentially arbitrarily large, which is why A* must be run within each.
What I'm angling for is an intermediate segmentation of zones (not burrows) whose size is limited in such a way that creatures don't need any planning/search at all to move within each. A* is run on this much smaller set of zones. They must additionally fulfill the criterion that there's an acceptable limit to the inefficiency (in wasted steps) incurred when navigating this way.

Even the most simple segmentation imaginable - dividing the map into 2x2 zones - would decrease the search and connectivity graph complexities by a factor of 4, though I don't know what the efficiency loss would be exactly.
Logged
Alpha version? More like elf aversion!

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #18 on: July 07, 2009, 01:22:00 pm »

Sunken,

There have been some hyper-efficient suggestions about connectivity graphs, which works really well in a room and corridor arrangement (basically, each room has a cost to cross from each door to another door, and pathing is cached for those costs, so from point A to point D, you path to the door to B, know the cost through B to C, know the cost through C to D, and that's your path cost to compare with  A-E-F-D).  The problem is, it's useless unless there's  a lot of choke points, and thus relies on player dungeon design to be efficient.

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #19 on: July 07, 2009, 02:22:57 pm »

Right, but that again is an optimal solution. What about relaxing optimality? Have quadtrees been explored, for example?
If free space was subdivided by quadtree, each tree leaf would be a node in a connectivity graph. The cost of traveling between adjacent squares could be approximated by its upper bound. Alternatively, the interfaces between squares could be the nodes. This is an approximation so the path would not be optimal, but one could set an upper limit to the inefficiency.
And once the dwarf is in a square, moving along his planned path, he can optimize his local planning, since that's less expensive - he can plan the optimal path 2, or 3, or N squares forward. I think this could be done so that it'd be difficult to tell that the dwarfs are not precisely optimal.

The quadtree shouldn't be too much work for the CPU to maintain either. Changes are localized. The connected components can remain on top of the tree unchanged, except for being quicker to update.
Logged
Alpha version? More like elf aversion!

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #20 on: July 07, 2009, 02:51:18 pm »

You're still missing the core issue, which is intelligently dividing space up into discrete units.  Until you've got a plan which does that, you aren't going to beat A*

Silverionmox

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #21 on: July 07, 2009, 03:28:02 pm »

Is A* faster, relatively, when pathing through smaller areas? eg. Is finding a way through two areas of size 10 faster than finding its way through one area of size 20?
Logged
Dwarf Fortress cured my savescumming.

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #22 on: July 07, 2009, 03:43:37 pm »

A* is faster is you can guarantee a midpoint(s).

AKA, if you're at point A in a huge room, and you know you've got to go out through either door B or C in order to get to point D.

There are some efficiency gains knowing you need to go to either B or C first (because A* knows where it's going, so it won't slither around in the room after it finds the optimal path to get the door.)



Code: [Select]

    ##############
    #            #
    C       A    #      D
    #            #
    ##############


By my understanding, A* will head straight to D and bang up against the wall.  It will check pretty much every point in the room before it heads to C and out the door and around.  If the algorithm 'knows' it must go through C to get to D, A* A-C-D will immediately and efficiently find the right answer.

The question is then... Can you find a way to 'know' you have to go through C that is more efficient to track than just A* every time?

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #23 on: July 07, 2009, 04:04:46 pm »

You're still missing the core issue, which is intelligently dividing space up into discrete units.  Until you've got a plan which does that, you aren't going to beat A*
You misunderstand me. I'm not talking about "beating A*"; A* is still being used, but it isn't run over map cells but on the higher-order units.
As for dividing up into discrete units, I already suggested quadtrees as a representation, which also implies a straightforward algorithm.
But quadtrees are not necessarily a good solution; it would be better to use something that can use heuristics for how DF spaces are typically structured - while still working on atypical shapes.
I'm thinking about one idea at present but for now I was only wondering whether this path has been trodden previously.
Logged
Alpha version? More like elf aversion!

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #24 on: July 07, 2009, 04:13:57 pm »

The question is then... Can you find a way to 'know' you have to go through C that is more efficient to track than just A* every time?

Human minds do this largely in terms of more or less discrete abstract places. Humans are also very likely to come up with suboptimal plans - and, indeed, different paths between A and B and between B and A, respectively. We use heuristics like "first get on the highway, then head towards B" and then don't think about B any more while heading for the highway. This lets us come up with a plan quickly, even if it's suboptimal. Only if it seems really off will we start to optimize it.
If the dwarfs turn out no stupider than people in this respect, slight inefficiencies are acceptable IMHO.

Edit: The above is just a little musing, not a suggestion :) We don't have to establish a full cognitive map, but neither should we let complete optimality restrict us.
« Last Edit: July 07, 2009, 04:16:17 pm by Sunken »
Logged
Alpha version? More like elf aversion!

Silverionmox

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #25 on: July 07, 2009, 05:23:21 pm »

A* is faster is you can guarantee a midpoint(s).

AKA, if you're at point A in a huge room, and you know you've got to go out through either door B or C in order to get to point D.

There are some efficiency gains knowing you need to go to either B or C first (because A* knows where it's going, so it won't slither around in the room after it finds the optimal path to get the door.)
Code: [Select]
    ##############
    #            #
    C       A    #      D
    #            #
    ##############
By my understanding, A* will head straight to D and bang up against the wall.  It will check pretty much every point in the room before it heads to C and out the door and around.  If the algorithm 'knows' it must go through C to get to D, A* A-C-D will immediately and efficiently find the right answer.

The question is then... Can you find a way to 'know' you have to go through C that is more efficient to track than just A* every time?
For rooms with a single exit/entry, dwarves exiting or entering that room will have to go through that point. Since we already define many rooms, the location of that single exit might be stored for each room. This will work better as soon as workshops, zones, stockpiles etc. can be defined by flowing out from a point, like bedrooms are. When you tell it to expand, and it can't, the game knows that rooms is closed and can check the wall, ceiling, floor. If there's only one opening (or stair), bingo!

Burrows can have the same done to them, though there's almost certainly more than one exit/entry. They'll likely have chokepoints inside them, though.

Depending on the level layout, there also can be just a single way up or down.

Burrows will prove to be a huge improvement for saving CPU time. Mining tunnels significantly slows down the game, because all the dwarves that have no business there (85-90%) try to find their path through them anyway.
Logged
Dwarf Fortress cured my savescumming.

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #26 on: July 07, 2009, 08:17:22 pm »

The question is then... Can you find a way to 'know' you have to go through C that is more efficient to track than just A* every time?

Human minds do this largely in terms of more or less discrete abstract places. Humans are also very likely to come up with suboptimal plans - and, indeed, different paths between A and B and between B and A, respectively. We use heuristics like "first get on the highway, then head towards B" and then don't think about B any more while heading for the highway. This lets us come up with a plan quickly, even if it's suboptimal. Only if it seems really off will we start to optimize it.
If the dwarfs turn out no stupider than people in this respect, slight inefficiencies are acceptable IMHO.

Edit: The above is just a little musing, not a suggestion :) We don't have to establish a full cognitive map, but neither should we let complete optimality restrict us.

When I say beat A*, I mean raw A*.  A plan grouping areas would be a good way to improve (as previously mentioned), but in order for it to do that you need a group where mapping from one group to another was at least generally better than plain A*.  You haven't done that.  (Also, you'd need an octtree, not a quadtree).  And Yes, it has been discussed.

Silverionmox:  I agree with you.  There's a lot to that.

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #27 on: July 08, 2009, 03:14:17 pm »

When I say beat A*, I mean raw A*.  A plan grouping areas would be a good way to improve (as previously mentioned), but in order for it to do that you need a group where mapping from one group to another was at least generally better than plain A*.  You haven't done that.
Just to be clear, I take it that by "mapping" you mean "pathfinding", not an isometry? (If so I don't follow you...)
No, I haven't proven such a thing. Quadtrees were just a simple example that required little explanation. As far as I can tell, pathfinding over a quadtree of free space in 2-D would in the worst case be equivalent to raw A* in search complexity; also, in the worst case (though not the same worst case!) it would produce less efficient paths by a factor of up to sqrt(2). Not terribly impressive, but it should be easy to do better.

Quote
(Also, you'd need an octtree, not a quadtree).
Only for flying creatures (for walkers, the floor would ensure that no zone would be higher than 1 anyway) - and AFAIK the current system doesn't pathfind for fliers, correct?

Quote
And Yes, it has been discussed.
I suspected as much but I haven't found anything by searching. I was hoping someone involved in such a discussion would give me a hint.
Logged
Alpha version? More like elf aversion!

tsen

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #28 on: July 08, 2009, 05:09:06 pm »

Dunno about you guys, but I'd accept somewhat less efficient movement on the part of my dwarves in exchange for less processor time usage. I don't expect my dorfies to be robots. Except when I tell them to mine.
Logged
...Unless your message is "drvn 2 hsptl 4 snak bite" or something, you seriously DO have the time to spell it out.

Fieari

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #29 on: July 08, 2009, 05:15:50 pm »

The current system DOES pathfind for fliers... but only if the destination is possible to be walked to.  Example:

Code: [Select]
1 F # F 2
F F # F F
F F # F F
F F F F F
F F F F F

If F is floor, # is air, you're at 1, and want to get to 2, then if you can fly, you'll go:

Code: [Select]
1 - - - 2
F F # F F
F F # F F
F F F F F
F F F F F

Instead of:

Code: [Select]
- F # F -
- F # F -
F - # - F
F F - F F
F F F F F

But if you have:

Code: [Select]
1 F # F 2
F F # F F
F F # F F
F F # F F
F F # F F

Then even if you can fly, the game won't let you get from 1 to 2.
Logged
Pages: 1 [2] 3