Hello blender artists, I have just recently started on an RTS project and thought I would just make some terrain, create a navmesh and be on my way to destroy the other players on the map! Ha! no not really. I couldn’t get passed the simple pathfinding problem I asked about a week ago. So begins my journey. I have looked every place on the planet for an AStar BGE example. To my dismay I could not find one, at least not one that I could understand enough to implement myself. So I started researching A* and found this very useful tutorial. http://www.redblobgames.com/pathfinding/
What I have in the .blend is a very simple example that I hope will be helpful.
I will be updating my progress as I accomplish my goals for what I hope to be a good RTS pathfinding.
Notice in image 1 how the path avoids the black tiles.
I still have a lot of work to do before this is ready to use.
Please note that the individual tiles that make up this grid are for testing purposes only and hope to use a single plane with only four vertices in a later version. I have tested this idea already and I don’t think it will be much more difficult to implement. It would also allow for a much larger map.
Here is the blend. AStar v1.03.blend (578 KB)
Nice! It seems that many people are interested to implement A*. It’s fine for small grids, however it begins to be very slow for more important grids (especially in python). You can find better algos here: https://github.com/qiao/PathFinding.js/tree/master/src/finders if you want to test. I made a try with Jump Point search algo a while ago and it was very fast.
The A* does not apply to BGE. The BGE is a game engine. The A* applies on weighted graphs (grid is a special form of a graph).
So you create a graph your A* implementation can act on. As you need to implement it in Python, you do not need the BGE for development or testing. You need the BGE to create you graph :D.
Well done on the A* algorithm. It took me quite a while to get mine right.
I agree with Youle that A* is not a great choice if your making something like a grid based RTS game with either;
A: a lot of unit
B: a large grid
If you’re using a small grid (50x50) and few units (under 20) then it can work, but otherwise you’ll need to investigate other algorithms.
There are some advanced ones, but they all rely on processing a lot of tiles in a short amount of time, creating processing spikes which can disturb gameplay.
For my own project I chose a simple nearest neighbor check for “dumb” swarm type navigation (combined with a short memory to avoid going back and forth between equally scored tiles). The game will feature a fairly open play area with no dead ends so the lack of sophistication doesn’t really matter.
I’ll be using a node based A* pathfinder on top of this if/when I decide to create more complex maps. In that case I’ll add an extra layer between the player and the units so that it gives the units an A* path (a list of waypoints) to the destination and they use their dumb pathfinding to navigate from point to point along the path.
