I need pathfinding for a 2D game with very large levels. Due to the size it’s important that the navigation graph is not grid based, and on the other hand can be created dynamically during runtime.
I like working with the “A* Pathfinding Project” (A* Pathfinding Project Pro | Behavior AI | Unity Asset Store ), but the only dynamic, non-grid-based option uses the Recast algorithm, which if I understand correctly only works with 3D colliders.
Does anyone know, if that can be adapted to also work with 2D colliders? Or alternatively, are there any good options for 2D pathfinding which do not use a grid?
I don’t know if it’ll help much, but I use grid-based pathfinding with the A*PProject. here are the GridGenerator and Editor.
using UnityEngine;
namespace Pathfinding
{
/// <summary>
/// GridGraph Subclass for ....
/// </summary>
public class UnityGridGraph : GridGraph
{
/// <summary>
/// Override of RecalculateCell from A* system.
/// </summary>
/// <param name="x"></param>
/// <param name="z"></param>
/// <param name="resetPenalties"></param>
/// <param name="resetTags"></param>
public override void RecalculateCell(int x, int z, bool resetPenalties = true, bool resetTags = true)
{
#if UNITY_EDITOR
if (!Application.isPlaying) return;
#endif
var node = nodes[z * width + x];
var pos = GraphPointToWorld(x, z, 1);
node.position = pos;
//note that values in pos variable are 1000 x too big due to precision multiplier in AStar - see Int3 struct
var realPos = new Vector3Int
(Mathf.FloorToInt(pos.x * Int3.PrecisionFactor),
Mathf.FloorToInt(pos.y * Int3.PrecisionFactor),
0);
node.WalkableErosion = node.Walkable = TmDb.IsWalkableAstar(realPos);
if (resetTags)
node.Tag = 0;
}
}
}
and the editor (not much there, but it belongs in an Editor folder of course)
namespace Pathfinding
{
/// <summary>
/// Editor
/// </summary>
[CustomGraphEditor(typeof(UnityGridGraph), "Unity Grid Graph")]
public class UnityGridGraphEditor : GridGraphEditor{}
}
The one part you’d need is seen in this line: TmDb.IsWalkableAstar(realPos);
It’s a bit of an oversimplification but that method looks in a HashSet with all positions that are nonwalkable.
That HashSet is filled when a level is loaded.
This is for a top-down view, turn-based game where a player moves one grid position at a time.
One caveat, I haven’t touched this project in several months and A*PP may have changed something. But this might provide a starting point.
Thank you for your reply! Unfortunatelly I need to avoid a grid-based solution because the levels will become very large. Nonetheless I really appreciate your quick response!
Although its a large map, are there a limited amount of places or nodes you need to pathfind between? For example a few towns, villages, crossroads, ruins or a list of places that need to be considered to find a path to?
If so, you can use Astar, but build your own nodes list in a data structure, rather than using cells or maptiles etc.You could point back to a map location within you node data structure.
Even if its a large number of nodes, you could put them all in a list and pathfind amongst them pretty rapidly.
Thank you for your input! I will investigate if manually placing waypoints can help me here, but in general I need pathfinding between arbitrary points, so limiting the places for pathfinding is not really an option.
Thanks for your reply, but I beg to differ on that point. Regular grids are not the only basis for pathfinding. Besides the waypoints that @SeerSucker69 described, a decomposition into irregular triangles is widely used. For example in the Unity NavMeshes or the mentioned “A* Pathfinding Project” asset.
I would like to use that approach, but onlly using 2D colliders (ideally with “A* Pathfinding Project”).
You are right, there is a mode which uses a grid, but the A* Pathfinding Project also offers non-grid based modes like Recast, Navmesh and Point based graphs. It is my understanding that grid-based pathfinding is less suitable for very large worlds. In your first answer you wrote “if your 2d lvls are big even the more reason to use a grid”, could you elaborate on that why a grid-based solution would be better here than a Navmesh based one?
Hello AngryProgrammer!
Thanks for your reply! Unfortunatelly I don’t really understand what you mean. I’m trying to find a way to do pathfinding without being based on a grid (I would like to use a Navmesh based solution, but for 2D). I’m not sure what you mean by “result you translate to visual effect on grid or anything you need”.