Alternative pathfinding


#1

This is not a request, but a discussion.

There can be two other ways to make pathfinding instead of navmesh.

  1. Nodes :
    you place the nodes and connect them to fit your level. There is no restriction, you can place nodes indoor, outdoor , nodes up and down.
    Path finding is very fast, it’s ideal for small scale action levels, multi height levels, puzzle games, strategy.

  1. Grid :
    you choose origin, dimension and resolution, the grid is baked on top of level (usually raycast down to detect geometry), most of the time the grid is top down and does not work mixing indoor outdoor or multi height level.

https://www.redblobgames.com/pathfinding/a-star/introduction.html

I think it could be good for Armory to support those features that can be useful and sometimes more appropriate when you need more fine tuning on navigation points instead of using navmesh polygons.


#2

Could you go a bit more in detail on the nodes option. I understand how this would work for patrolling type enemies. You would just set the which node to go to and in what order. But what happens when the player is detected? Does the enemy move from node to node toward the player? How is the best route determined as the player keeps moving? It seems like a very simple set up, just trying to figure out the details of how it might work.


#3

I’m wondering if this would be the same as just manually creating the vertices of the nav mesh. Is there anything stopping you from creating a simple nav mesh manually by placing the vertices?


#4

When two nodes are linked it’s a path.
When some character needs to move near the player, it finds the nearest node where the player is and call an algorithm that will give it the shortest path.
When there is other dynamic characters on the path, the characters avoid them on sides and continue on it’s path from node to node.

Like Navmesh you code how many times during some period the enemy re check player position and re calculate the best path.
With nodes, until the player moves and the nearest node change, the enemy stay on the calculated path without needing to recalculate.
It’s something very common.

Navmesh is heavy api , and path is calculated on polygon vertices, the character will follow polygon edges , while node allow you to create a better path that is better aligned in space and does not follow polygons vertices and edges limit.


#5

Here is some version, it would need to be translated to Haxe, i’ll check it later.

http://www.jgallant.com/nodal-pathfinding-in-unity-2d-with-a-in-non-grid-based-games/

The twin stick demo i started was about small levels with obstacles, grid looks like best suited.

Or this one