[Adonthell-devel] Pathfinding in 3rd dimension

[Kai Sterker]

Y'all,

having finally warmed up, I'll be looking into one of the remaining
issues needed for WE: making pathfinding aware of the 3rd dimension.

So far it only works for ground level pathing, but Redwyne Inn will
have cellar, first and second floor at least, with NPCs walking around
on either (and sometimes between). So I would cut the task into 3
phases, hoping to complete at least the first two.


1. Pathfinding on levels other than 0.

Simple. Introduce a z-coordinate other than 0 into the pathfinding
system, so characters can walk around on their respective level.


2. Level changing using stairs/slopes.

Not quite so simple any more. Need to figure out where levels can be
safely changed by walking up/down stairs or slopes. Am not even sure
how to best go about this, but preferably it should work without
having to explicitly point out to the pathfinder what is a stair and
what isn't.


3. Jumping/climbing/falling

Probably quite hard. Maybe could be divided even further. Jumping
across gaps, jumping up to a higher level. Dropping down to a lower
level. The few thoughts I had about this is that jumping should
generally have (much) higher costs, to encourage NPCs to use bridges,
stairs and natural slopes instead of cutting straight through
difficult terrain. Also would suggest to make the grid used for
pathfinding larger in Z-space as it is on the ground. At least as
large as a character can jump, which is about 40px - 50px. The current
pathfinding code already checks for holes and obstacles. This seems to
be a good place to try and see whether a jump/climb/drop would work
there.

This might cover actually finding a path that includes
jumping/climbing/falling, but more work needs to be done when finally
executing that path. I guess during the pathfinding stage, special
"commands" could be stored in those nodes where a jump is required.
But I guess we'd also need checks if we're still on the correct path
or if the jump/fall took us somewhere where we didn't expect to end
up. In that case, we'd have to update or recalculate the path to our
goal.


Comments welcome. As today is my last day off, things will go more
slowly from now on. But I should find time on the weekend at least.

Kai