Legacy GM Grid-Based Pathfinding in Three Dimensions

[Lumenflower]

I'm currently working on a project in which the player can build a small, multi-levelled environment (think FTL with several layers) and certain 'minions' navigate it autonomously. Successive floors are connected by staircases. The problem is that I don't know how to approach writing the pathfinding scripts for these minions.

I'm experienced in mp_grids and the related functions but I feel like a more adaptable, custom setup would be required here. It's clearly not as simple as just seeking out a set of 'up' or 'down' stairs and navigating to them, as there's no guarantee that this would produce an efficient (or even possible) path.

It seems the most effective method would be to use a node-based map of the environment and write a custom pathfinding algorithm to navigate it. I have a good idea of nodes and pathfinding in a mathematical sense but I have no idea how to store and retrieve the information involved effectively in GM. It seems each node would require a bunch of information such as an index, x, y, z, and some list of all the nodes it's connected to.

Anyone who's approached this challenge before - how did you tackle it? I'm sure all I need is a push in the right direction and I'll give it a bloody good go at figuring out myself

~Druid TC

 

[lolslayer]

There are 2 ways to solve this, A* and waypoint pathfinding (probably what you call the "nodes")

For A* you shouldn't come to me for help, but I can help you with the waypoint mechanic, I've been thinking for a long time and I think I know how to implement it in 3D, I don't like to share my ideas on it publically but I'm always open to help people if they ask for it personally, if you want to, ask me to add you on skype in a PM, I've got some 2D waypoints working atm and I can help you with the 3D implementation, I've got a lot of school to do atm but in 1 and a half week I'm finished with school and then I can take a look at it myself

 

[elementbound]

I think you are overthinking this. There are two cases:

• Destination is on the same level -> easy, just go there
  
• Destination is on different level -> walk to an arbitrary staircase. This can be the nearest ( as in point_distance nearest ). Once there, do this again. Obviously, if destination is higher up, an upward staircase is needed, if destination is below, a downward staircase is needed.

There. You can use mp_grids for this.

As for A* and any other node-based setup: if you use a ds_queue, you can just queue x,y,z variables ( so the queue sizes is <queued nodes>*3 ) and dequeue them in reverse order. Every node will link into the same layer, the staircases will also link up/down. But I think this could be slower, as the algorithm may not necessarily march to the nearest staircase. You'd need a clever heuristic for that.

 

[Lumenflower]

@lolslayer I'm out of the country (and away from my PC) until mid-August but I might just hold you to that one when I get back sounds really interesting, so I'll look up waypoint pathfinding in the meantime. Good luck with your project

@elementbound that would work in a simple setup, but in some situations that wouldn't produce the most efficient path. Picture two towers next to each other - to move from the top of one to the top of the other, you'd have to first descend to the bottom, then ascend the second tower despite only needing to move to a destination on the same level.

 

[elementbound]

In games you rarely need the most efficient path, just a "good enough" path. Although I can see the problem with the tower example.

 

[FrostyCat]

Treat nodes as maps with x, y, z and a sub-list of connected nodes. Then you can push the nodes onto priority queues for A*/Dijkstra's and characterize paths as arrays or lists of nodes all you want. It really isn't all that scary if you are already versed with 2D methods.

 

[lolslayer]

Treat nodes as maps with x, y, z and a sub-list of connected nodes. Then you can push the nodes onto priority queues for A*/Dijkstra's and characterize paths as arrays or lists of nodes all you want. It really isn't all that scary if you are already versed with 2D methods.

A*/Dijkstra isn't really the fastest way of pathfinding if you play on big maps though

And thank you Druid TC, ask for help anytime you want

 

[FrostyCat]

How big the map is shouldn't be a factor if the model to use A*/Dijkstra's on is based on critical points only (in this case, staircase entrances and exits) as opposed to a full navigation mesh. Being a smart programmer means picking your battles and knowing when to use a naive model or not.

 

[lolslayer]

How big the map is shouldn't be a factor if the model to use A*/Dijkstra's on is based on critical points only (in this case, staircase entrances and exits) as opposed to a full navigation mesh. Being a smart programmer means picking your battles and knowing when to use a naive model or not.

True

 

[lolslayer]

I think that an AI using "nodes" is a better way then to call it an AI using "waypoints", after a quick search on google I found out that the term "waypoints" is also used to just create a fixed path using waypoints (I just want to say this before I feed anybody with wrong terms )