Free 3D Pathfinding using a navmesh and A*

Kentae

Member
3D Pathfinding using a navmesh and A*
v1.1
Hello my beloved community!

This is a 3D pathfinding system that uses the A* Algorithm on what is called a Navmesh to find the shortest, or reasonably short, path from Point A to Point B.
The system also utilizes something called the Funnel Algorithm to optimize that path in such a way that all agents should find their way in a fairly natural maner.
The Navmesh itself can be created in any 3D software that can export to .OBJ. Then that .OBJ is used to create the Navmesh data structure in game maker.

Here are a few screenshots from the demo that you can download below:
kt_navmesh_system_screenshot_001.jpg
kt_navmesh_system_screenshot_002.jpg
Showing the navmesh over the visual dungeon model.
kt_navmesh_system_screenshot_003.jpg
Showing the octree.
kt_navmesh_system_screenshot_004.jpg

And here is a video showing the system in action:

This system is still a Work in Progress but should work if you want to test it out. It doesn't require too much work to implement as only a few scripts needs to be called.
I would be very happy if those of you who decide to test it reports any issue you may find to me, either here or via PM.
You can find both a stand alone executable of the demo and a .yymp, that you can import to an empty project in game maker, below.
(You should not import the whole .yymp into your own projects yet as all the objects, rooms, sprites and such are still in it and would clutter up your project.
You are better of loading it into an empty project and chicking it out there first)

You can now also find a .yymp that only includes the scripts needed for the system to work. This one should be fine to use in your projects :)

Currently known issues:
- The pathfinder some times make weird decisions around certain corners, where it seems to have failed to remove an unnecessary node.
(I belive this one has now been fixed. The issue was located in the funnel algorithm the system uses to optimize the path. The issue occured
whenever both funnel edges pointed in the same exact direction. The system could then not figure out wich edge was to the right and wich
one was to the left.)

- Some times the agent stops following the path and continues into oblivion.
(I'm gonna call this one fixed too, as I've not been able to reproduce the issue.)
- You can't recalculate the path for an agent that has, for any reason, gotten too far away from the navmesh.
(This is best fixed by having a gravity and/or collision system to keep them on the ground)

Things I want to add:
- The possibility to use this system with spherical game worlds, like planets. (This is currently restricted by how the funnel algorithm is implemented)
- (I'll add more things to this list as I come up with them)

So far the system has only been tested on one computer running windows 10.
I see no reason why it shouldn't work on other platforms though.
The system was created in GMS 2 and might not work as expected, or at all, in GMS 1.x

I tested it with 50 active agents, all finding their paths simultaniosly, without any real lagspike or fps drop.
Mind you that this was tested on a fairly powerfull computer and there should never be any real reason to have that many agents
find their path at the same time. Especially since the system is built in such a way that several agents can use the same path if need be.

The actual Navmesh used in this demo was made manually by me in Blender and that is currently the only way to make them.
There is no system or function for automaticly generating them included in this system.
A thought I've had is that, since Blender has it's own built in game engine, there might actually be a way to generate navmeshes there. Then you would
just export the resulting mesh as an .OBJ and use that to create the Navmesh in game maker. This is just speculation though.

Download links:
Stand Alone Executable:
.yymp file with the whole demo in it:
.yymp file containing only the Pathfinding system and needed scripts:
https://www.dropbox.com/s/rlavsbo47isx6w1/kt_navmesh_system_v1.1.yymp?dl=0

As I said in the old main post (see below) this system is completely free and you can use it in your projects as you want.
All I ask in return is that if you should make any improvements and/or additions to the system or if you fix some issue with it, you post it here
in this thread so that all may benefit from it.

Please do not be affraid to ask if you have questions about this system :)

Here is the old main post:
Hello my beloved community!

As the title would suggest, I have spent my time in isolation creating a 3D Pathfinding system using a Navmesh and the A* algorithm.
The system creates a navmesh and it's required datastructures from a .OBJ file. So it works similarily to loading a simple .OBJ model file except it only takes the parts it needs from it (vertecies and face data).

Now I will say that the system is not complete yet, wich is why I post it here in the WIP section.
It is not a perfect system, but it does work, and it does give me, personally, what I want from a pathfinding system.
In other words, it will find a decent path from point A to point B and it does some smoothing to the path before it's returned and ready for use.
Now as I said earlier, the system is not perfect, as you will be able to see in the video linked below.
I do however think that I've gotten far enough to feel that it's worth showing of at this point.

Now, before I show you the video I would like to mention a few things.
There might seem to be some "lag" between placing the start- and end-points and when the path has been calculated and is visualized.
This is not the case! I've just made the demo in such a way that I place the points with left- and right- mouse clicks and then have to press space to start the actual pathfinding.
This means that the system is faster than the video might suggest.
I just wanted to clear that up :)
Also, I wont post any code or demo just yet, as the system is currently only at a point where it works, but is in very few ways user friendly or optimized.

Now here's the video, enjoy! :)

I will continue working on this system in the days (probably weeks) to come and I'm going to have to rewrite a good portion of it to make it... well, usable for other people.
I will also try to "separate" the octree system from the navmesh system. I found out during the development of the system that the octree could easily be used to make a nice, fast and separate 3D collision system.
What I mean with that is that, currently, the navmesh system relies on the octree system, and will continue doing so, but the octree system is also woven into the navmesh system. In other words, one cannot exist without the other right now.
So I'm going to make it so that the navmesh system uses the octree system but not the other way around, freeing up the octree system to be used for other things as well :) (if all that makes any sense)

My goal with this project is to give the community a decent and reliable 3D pathfinding system.
And yes, that means it's going to be for free :) This community has helped me so much over the last... well, holy s**t, 15-16 years that I wanted to at least try to give something back ^^
My only request is that when I make the sorce code available, any and all improvements, additions and optimizations made to the system will be posted in this thread so that everyone can benefit from them :)
I will also do my best to update the main post as the system is updated.

Thank you all and see ya later ^^
 
Last edited:

Kentae

Member
Hello guys :)
I've finally gotten around to updating the navmesh system and uploaded a demo of it.
I have updated the main post too, so please check that out for more info ^^
You will also find the download links there, have fun! :)

Edit: I forgot to say that I'm really sorry it took so long for me to get this done. I've had my plate quite full lately, being back to work
and paying my girlfriend some attention after spending so much time creating the initial system hehe :p
 

Kentae

Member
Update! v1.1

Hello again guys, I've updated the system once more :)

But first here's a new video of the system in action (Also added to the main post):

I've also added a .yymp file that only contains the pathfinding system and the required scripts:
https://www.dropbox.com/s/rlavsbo47isx6w1/kt_navmesh_system_v1.1.yymp?dl=0

What has been fixed in this version:
- Fixed an issue where the system seemed to add an unecessary node to the final path. (Previously thought to be a failure to remove a node)
- Fixed an issue where an agent following a path some times stopped following the path and instead went off into oblivion.

For more info check out the updated main post :)
 
Top