1
\$\begingroup\$

What methods do you use to handle path finding in non-tiled 2D games? Tilemap based methods can use A* and 3D has NavMesh available. The only success I’ve had is with raycasts but it doesn’t seem like a great way to handle things with hand draw sprites or uneven terrain.

\$\endgroup\$
5
\$\begingroup\$

There is nothing about A* that is specific to a tile map or grid. A* is usable in any kind of directed graph so long as there is a usable heuristic - e.g., distance to destination. When there isn't a good heuristic to use, recall that A* is just a specialization of Dijkstra's, which likewise can be used on any directed graph.

The only thing A* thus requires is a node and a hueristic. With a tile map, the nodes are the grid locations. With a navigation mesh, the nodes are based on the mesh geometry. Some games have used explicit nodes placed in the world (either automatically or even manually) which is essentially just a generalization of a navigation mesh.

There's also no reason you couldn't use a navigation mesh in 2D. Note that 2D is just a subset of 3D (set the Z axis to 0). Navmeshes most certainly have been used (with A*) for decades in 2D games.

I'm not aware if Unity is imposing some kinds of limitations here; if if is, you're certainly capable of writing A* or nav meshes yourself without using whatever Unity provides by default.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

This is a rather broad topic, so my answer will be rather high level.

General path finding algorithms (including A*) find a shortest path on a weighted graph in which the vertices (aka nodes) represent locations & edge weights represent a cost (typically related to the distance between the nodes.

In a simple tile map, generating the graph representation is usually done as follows:

  • each tile (or center thereof) is a node
  • adjacent neighbors share an edge

One solution for non-tiled 2D games is to impose a tile map on the area of interest. If your virtual tile is 20x20, you simply do integer division on a coordinate location & use that to look up the tile. In some cases, this works fine, but it has limitations - namely the trade-offs between resolution & performance.

The other common solution is to generate a navigation mesh. At a high level, this basically means:

  • decomposing the area of interest in a polygon mesh
  • establishing a corresponding weighted graph
  • applying some path finding algorithm

enter image description here

The challenge with a navigation mesh is finding a good decomposition. There are ways to automate this, but it's not uncommon to need to fine tune things.

Finally, as you pointed out, you can also do raycasting. I've done this once myself for a research project. I had a static 2d map & for every corner, I did raycasting to other corners. Essentially, the corners became my nodes & rays that didn't clip anything became edges.

enter image description here

While this was appropriate for that particular problem, it also has some challenges. Specifically, if you have N vertices, there are potentially N2 edges. Also, you usually can't travel exactly on the edges of your obstacles, so you may need to adjust for that as well.

Amit P has a great tutorial on path finding that covers this & many other details (and is the source for the illustrations used here).

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

A* works for all graphs, not just grids. "Nav meshes" are just a method of forming a graph for maps that are not tilemaps, and should work equally for 2D and 3D.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.