I've looked through some A* pathfinding algorithm examples, but as far as i know they work with grids e.q -> http://qiao.github.io/PathFinding.js/visual/
But how can I use this algorithm in my 3D Engine(I'm using Unreal Engine 4)?
\$\begingroup\$ \$\endgroup\$
1 
- \$\begingroup\$ You overlay a 2D grid on the 3D world. Look at how the A* project in Unity does it. Btw, A* isn't limited to grids only. \$\endgroup\$user15805– user158052015-01-30 10:09:39 +00:00Commented Jan 30, 2015 at 10:09
Add a comment |
1 Answer
\$\begingroup\$ 
\$\endgroup\$
2 Actually A* does not use dimensions.
A* works with nodes and each nodes have paths to other nodes.
In the case of a 2D grid every cell is a node and every boundary is an implicit path (left, right, up, down, and/or diagonals), the key here is that it is implicit.
This is a trick to reduce the memory footprint, but A* itself does not require a 2D or 3D grid. You can use A* with explicit paths/connections between the nodes such as a country road map.
In the case of a 3D grid, you apply the same method as a 2D grid but now you can move in the 3rd dimension as well.
But this is not how most 3D games use A* because the memory needed for a usable 3D grid becomes too large very quickly. Instead they use navmeshes.
Search the web for "navmesh"
Blue part is the navmesh:
A* works on those: each triangle is a node, each edge is a path.
There isn't an up-down-left-right, there are neighboring triangles through edges A-B-C.
answered Jan 30, 2015 at 12:47
Stephane Hockenhull
12.1k1 gold badge26 silver badges44 bronze badges
- \$\begingroup\$ will be the center of a triangle used as point for the pathfinding? and is this done with some kind of earclipping to get this navmesh? \$\endgroup\$jeromintus– jeromintus2015-11-17 16:15:10 +00:00Commented Nov 17, 2015 at 16:15
- \$\begingroup\$ The edges of the triangles are the connections, the triangles are the cells. Once a coarse path is found through the triangle/cells the path is usually refined (straightened, smoothed) while still being within the triangles. Here's a related question that shows path smoothing examples: (gamedev.stackexchange.com/questions/81593/…) \$\endgroup\$Stephane Hockenhull– Stephane Hockenhull2015-12-05 04:47:56 +00:00Commented Dec 5, 2015 at 4:47