Print

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

[PencilinHand]

That's certainly an interesting idea. The subzone portion sound similar to the "Memory Efficient Pathfinding" paper Impaler linked to earlier.

I do have a few criticisms of your method:

Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same **.

This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.

Also, you're only reducing the graph by a factor of 3. The overhead from keeping track of the new abstract graph (and its subgraphs) is likely to be larger than any gains you have from abstraction. I don't see a way to easily increase the amount of abstraction, so I'm not sure we can solve this without significant changes.

I was hoping for criticism.

It is an idea, not sure about interesting but it is an idea.  I haven't read that paper, yet, I will try to in the near future.  I may have to just break down and write the code to test it so I can get it out of my head.  At the least it will allow me to do something somewhat more productive compared to my more recent endeavors. Besides, it should be good for a few laughs if I ever finish it and make it public, so that is a bonus.

I did note that the assumption isn't always true(see the "**" note).  My argument for the assumption is that exceptions would generally be rare and relatively minor.  Generally not more than a difference of a few tiles in the whole path when the exception happens.  It is a potentially unruly assumption, off hand I can think of one case especially.   However, I think it is too important for the abstraction to work to do without it.

I think non-uniform pathcosts could be supported but would have to be generalized(so it wouldn't be exact to the tile) in a similar fashion to the zone/tile connection abstraction between hierarchy levels.  In fact, it could be used to allow a user to optimize the most glaring exceptions.

I was thinking that layering the abstracting by 3x3 for each level(suppose 3 or 4 levels?) of a hierarchy.  The memory overhead would be higher but it might significantly reduce the CPU and memory cost during the actual pathing.  If you are feeling that it would merely balloon memory cost without noticeably reducing execution cost then it is likely to be a dead end.

You didn't mention the lack of consideration for novel modes of travel, like digging/destroying obstructions, swimming, flying etc.  Or was that what you meant by the non-uniform cost comment?

For novel modes of travel, I would think that there would need to be a different method all together.

I think my posts are excessively wordy without improving clarification or communicating significantly(much like the idea, HA!).

[zchris13]

You could make the program meta itself, occasionally check paths (say one every 100 paths) with A* or whatever, and fix the most glaring pitfalls.  Or, say, when you pause the game.

[Impaler[WrG]]

shadow_slicer got a successful path earlier today but we don't have trees correctly flagged as impassible and its supper inefficient and doesn't have proper output data yet.  Tomorrow I hope we'll have these issues resolved and we can start showing you screen shoots of paths.

[shadow_slicer]

Trees still aren't fixed, but here's a screenshot of a path below ground.

Spoiler: Screenshot (click to show/hide)

[Nexii Malthus]

Excellent progress!

[PencilinHand]

Trees still aren't fixed, but here's a screenshot of a path below ground.

Spoiler: Screenshot (click to show/hide)

Simply awesome!

--------
EDIT:

I have thought more about what I was proposing and have done a little research on it.  What if, instead of assuming exactly identical cost for all zones at the current hierarchy, what if A* were run one hierarchy level below what was being pathed over to generate a better approximate cost for a specific zone?

[CobaltKobold]

...I find it funny/great that you created a visualiser apparently completely incidentally to your task.

[Footkerchief]

The visualizer is Khazad.

[CobaltKobold]

I skulk corrected.

[Draco18s]

This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5.

6, actually:


Regions:

a b
c d

MetaPath: a -> b -> c

region layout:

###|...
###|...
###|.##
-------
..#|...
..#|##.
...|...



The path through region D costs 6.


65.
##3.5
12.

[Nadaka]

This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5.

6, actually:


Regions:

a b
c d

MetaPath: a -> b -> c

region layout:
###|...
###|...
###|.##
-------
..#|...
..#|##.
...|...


The path through region D costs 6.


65.
##3.5
12.

it actually doesn't. You can pass from position 5 to the next tile diagonally. You also count movement into and out of the area as movement through it, meaning the initial and final area have no movement cost. You should only count one of those two values for each area (it does not matter wich one, as long as it is consistant). The following diagram demonstrates the actual longest path through d.

##.|#..
##.|#..
##.|###
-------
###|...
..#|##.
...|...


edit:hehe, oops.

[Footkerchief]

Nadaka -- the use of [tt] or [code] tags will make your diagram much more legible, like so:


##.|#..
##.|#..
##.|###
-------
###|...
..#|##.
...|...

[PencilinHand]

Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.cost

The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).

I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.

You could....take the wordsright out of my mouth.

26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions, but I already found a corner case I'd like preserving: swimming up waterfalls. solvable if swimming is permitted to go up.

I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)

I almost hate to bring this up but the thought occurred to me.

It is actually 10 directions, for a dwarf in the current implementation at least and up to 18 for a flying creature.  The reason it is 10 for a dwarf is when they are moving between z-levels at an angle(can only happen at ramps) they CAN NOT move in the direction of the ramp and stay on the same z-level.  Also, they CAN ONLY chose to go either up or down a given ramp from one direction not both.  This is because of the way that ramps are defined, they MUST have empty space on the z-level above them if they are going down. They MUST have a blocked tile on the same z-level if they are going up.

In the case of flying creatures, they can choose to either walk down the ramp or fly in the empty space on the z-level immediately above it.

To test this, construct a small wall(a 3x2 will work) and build a ramp in the middle of one of the long sides.  Then deconstruct the single wall tile that the ramp is attached to.  Then try to station someone on the wall.  The test for down ramp is equally simple, just build a wall on the z-level above the ramp and watch the guy get stuck.

For a flying creature, it could be argued that there is no need for the extra eight slanting down paths.  All pathfinding should be accomplishable for every possible creature with only 10 direction movement anyway because of the way ramps are defined in game.

Depending on the way Toady has defined the construction options and if he adds any, will depend on if more than 10 directions would be needed in the future.

[Impaler[WrG]]

I think I'm going to write a graphic representation of the connectivity map, this is basically a bit-flag for each tile indicating which directions are movable.  Were going to support all 27 direction in the bit-field so the system is flexible but how the map gets interpreted into connectivity flags is really a separate issue specific to the client and so long as were not missing any 'real' connections or allowing blatantly wrong ones its not going to significantly alter the path found.

[qwertyuiopas]

27 is numpad's 9 times 3(up, down, and same-z)

HOWEVER, 5 + same-level = unchanged, making the true number 26, or solving the "stay in place" question.