2.5d Pathfinding

Hello to anyone that still uses these forums for Construct 2. I would greatly appreciate help with an issue I've been trying to solve using my 2.5d system. In short, my 2d game has a z-axis, which works phenomenally. However, the built in pathfinding is completely broken by it.

For starters, setting the obstacles as solids will not work, as the method of detecting if in object is solid is not based on the solid behavior, but on a variable attached to a family.

Setting the obstacles as custom will also not work, as it is impossible to only add picked instances as obstacles, you have to add every instance of the object.

Also, there is one shared "map" used for every object with the pathfinding behavior, meaning that what is an obstacle for pathfinders with 0 as their z-axis might be completely different from pathfinders with 100 as their z-axis.

Finally, the pathfinding algorithm was not designed to account for changing their z-axis. It will attempt to find a way to the target without accounting for layers of verticality at all.

To get around this I have considered using a navigation tilemap with the EasyStar pathfinding plugin, where I can set the availability of certain tiles/nodes by checking any solid sprites over them. However, just like the default pathfinding plugin, EasyStar was not designed for layers of verticality, and won't consider it when pathfinding.

What MAY potentially work is a custom implementation of the A*star algorithm, where the nodes themselves can be given a position on the z-axis. I will attempt to do this, but I would GREATLY APPRECIATE if anyone with existing A* experience or just general pathfinding or 3d construct experience could give me tips or pointers in the right direction. Hell, on the off-chance that anyone has attempted something like this before please link me to where I can see their work.

All help is greatly appreciated.

An event based AStar algorithm is quite doable. If you search for posts by me that mention “astar” you’ll find a lot of examples. I’ve seen other users post examples too on here.

If you want to make your own I’d recommend the site redblobgames. It is one of the best references of how to do it.

The part of the algorithm you’ll want to modify is the part that looks at the neighbors of a location. For grid based it’s the four directions. For hex based it’s six. For node based it’s whatever other nodes that are connected. And since it will be event based you can have the obstacles different for different purposes.

Haha, looking at your manual path.capx is what gave me the idea in the first place. I'll take a look at redblobgames, thanks for the info.

Now that I'm looking into it, the performance impact of pathfinding via events isn't negligible. Might there be a more efficient way of doing this?

I mean the example above is pretty instant with finding a path.

Besides events you can make a plug-in and do what you want with JavaScript. You can also run js with the browser plug-in if you want to do that instead.

Events just are easier and more flexible especially with interacting with other things in the engine. You can often improve performance by refining the algorithm used.

JavaScript can perform faster but you also have to deal with debugging it inside your game.

Probably any of my examples can be improved. I go to the point of getting it working a basically stop. There are things that likely can be changed to make it faster. Also if finding a path takes too long it can be changed to do it over multiple frames instead if need be.

The tweaks are endless. Probably the newer examples I’ve made are better. My goal is to make capx as simple as possible and do what is desired.

Write the algorithm in JS probably the best way to chase performance. ROJO has an example in JS too. Most pathfinding is not cheap CPU trade.

Interesting. I'll take a look at it if my implementation becomes too resource intensive. Can't seem to find it though, do you have a link?

Many thanks!