koobas.hobune.stream
2D Pathfinding: how to create navMesh
I'm developing a small 2D top-down strategy game as a hobby. Well at least I would like to, right now I'm only playing around with Unity.
I think that the first thing to implement is pathfinding. There are existing packages but I would like to roll my own. Although I'm new to unity, I'm not new to programming.
Here is an implementation of A* I did in python: https://youtu.be/pwevEL57c7Q
The algorithm itself is no problem, I could translate it to C# quite easily. The setup of the graph is difficult. And this is were I need feedback. I've got a few ideas, but I want to avoid investing time in something that is a dead-end.
Create an evenly spaced grid of nodes, create edges between neighbouring nodes. Each obstacle "registers" itself with the graph. The graph looks at the position and the size of the object and deletes intersecting nodes.
Create an empty graph. Each obstacle "registers" itself with the graph. The graph looks at the obstacle, queries its collider, creates a node for each edge of the collider and then loops through all existing nodes. For each pair of existing/new node the algorithm checks if there is something in the way, if not it adds an edge
Go overboard: Create an adaptively spaced grid (something like a quadtree). Start with just one square. If an obstacle is added, subdivide recursively. Stop the recursion when the ratio of obstacle/square is acceptable. Add nodes to each quad. Remove intersections with obstacles.
Each has its advantages and disadvantages.
Produces a huge number of nodes. The grid should be very fine-grained. This could waste a lot of memory. But creating edges is easy, since you know the spatial setup and know which nodes are potential neighbours.
Is very cheap to begin with. But as you add obstacles the performance will seriously degrade. For each new node, each existing node has to be checked for a clear path. I don't think that this is feasible.
Seems overkill for such a "simple" task. I've never implemented adaptive mesh refinement. Would surely be interesting but that can't be standard for every game, can it ?
Can you point me in the right direction ? Did you implement pathfinding for your game, too ? Where are the strengths and weaknesses of unity3d in terms of this task. For example: How many raycasts can I do per second in a complex scene with dozens of objects ?
