Pathfinding with shafts/elevators

8 posts

Flag Post

A mine layout might look somewhat like that. Obviously more complex, but this is for illustrative purposes. All vertical paths are shafts. (not like 1-2 on top of each others, I mean the tall ones 10+ long). This is a side view, so picture gravity is going down, sky and air is to the top – not shown in the picture. All destinations are able to be reached. There will never be a condition that they cannot be reached.

Going up and down these shafts are elevators. A miner needs to be able to travel from any point in the mine to any other point in the mine by traversing these elevators and walking on solid tiles. However, I’m not sure how I should be doing my pathfinding.

Should I go with A*? Or write my own? Things I am interested in having are having queues for each shaft (could be translated as a cost to use each one) as well getting to a place in the least amount of time.

If I write a custom one, should I do a depth based ( right word?) search, starting with the tile the miner is at, looking for shafts on that layer, checking to see if any of those shafts reach the destination layer, if not, check for shafts on the closest layer to the destination and repeating? Or a breadth based search checking all the shafts in the entire mine to see which shafts exist between the current tile and destination and selecting a path based on those?

Flag Post

Maintain nodes at all intersection points – choosing this to mean every mine tile that does not have exactly two adjacent mine tiles which are oriented as a triplet of tiles either horizontally or vertically (i.e. any tile with either: position N and S being a mine tile and position E and W not being a mine tile; or position E and W being a mine tile and position N and S not being a mine tile) would be perfectly fine, while excessive where non-cardinal direction movement is allowed. Then run A*.

A better approach for non-cardinal direction movement would be to use the one discussed here which should produce the following waypoints with appropriate edges:

From this map of nodes, you will be able to directly traverse from any mine tile to some node, in particular, your source and destination will always have line of sight to some node.

Depending on how you wish to implement your game, it may be more appropriate for you to only permit cardinal direction movement (as opposed to any direction in a plane). As such, you may want to treat the condition for a node as a mine tile accommodating a change in cardinal direction (note that this is identical to the statement in the first paragraph, although from a different perspective) – i.e. if we assign integer values to the cardinal directions such that N takes 0, E takes 1, S takes 2, and W takes 3, then a mine tile is a node if there is some mine tile in integer direction x and some mine tile in integer direction y where x%2 != y%2; they are ‘at right angles to each other’:

The extra simplification would be that edges can only be vertical or horizontal.
This implementation would have scope for pre-rendering, given the relatively low number of edges (which would be low anyway due to the fact that the layout of the mine tiles is such that cardinal direction movement is almost forced); just take care in making sure that no edge runs through a node

Essentially only you, as the designer, would know which nodes and edges are appropriate, and from your description, it sounds like a mix of the upper and lower implementation would fit, as you have the constraint of walking only on solid tiles; for example, any node which has a mine tile at position E and a mine tile at position SE is no longer appropriate for movement in direction E

Flag Post

The green dots you labeled (thought not shown well in the picture) have roofs and ceilings. Every horizontal path has a roof and a ceiling unless a shaft passes through that tile. (aka you can pretend that there is an a layer of dirt between them)

Nodes are a great idea, but I’m expecting the mine to be much much much more complicated than this. Pretty much it should be able to handle 4-10 nodes per layer as the game progresses. Which really isn’t a big deal since pathfinding won’t be run all the time.

As I’ve only coded A* once, with the help of a tutorial, I assume using Nodes instead of grid based tiles would just require me to directly link nodes? (aka the bottom red node’s up is the red node a dozen tiles above if in the same shaft)

Flag Post

Originally posted by UnknownGuardian:

The green dots you labeled (thought not shown well in the picture) have roofs and ceilings. Every horizontal path has a roof and a ceiling unless a shaft passes through that tile. (aka you can pretend that there is an a layer of dirt between them)

if that’s the case, typical A* is sufficient; every time the AI tries to move to a tile, call that tile’s interact function which will return a status for what the AI can do immediately and accepts a call back; if there is no wait period, the interact function discards the callback and returns 0 or whatever, otherwise it returns some other value and calls the callback when the AI can move onto that tile (this allows queues and not having multiple entities using elevators that don’t/can’t exist)

Flag Post

What do you mean by this 4-10 nodes per layer business?

What may be ill-defined right now is whether shafts can be stacked while remain distinct (if this is not allowed then that makes implementation easier, and obviously helps with the current graphical representation), e.g. whether the rightmost shaft beside the square of four green dots is two medium length shafts or one long one.
It’s not possible to distinguish from the diagram where you can move vertically and where you can move horizontally.

You’ll need to manually link the nodes with edges to the closest node in each cardinal direction, if there is one.

The nodes should be chosen such that there is a minimum number of them (roughly), and that every mine tile has a node in sight in one of the cardinal directions.

I’m missing a red dot in the first diagram, by the way.

Flag Post

Huzzah. Looks like its mostly working. I need to add weighted paths (elevator queues) now and optimize it a bit by only updating the nodes list and node’s neighbors list when a new area is mined out or a shaft is added.

EDIT Still buggy sometimes. :/

Flag Post

Last bump. Got elevators and pathfinding running. Its amazing. Also, lame gif cause the file size was super huge. Had to lower the framerate a ton and dimensions by half.

Flag Post

Lovely gif