2
\$\begingroup\$

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)?

\$\endgroup\$
  • \$\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 Jan 30 '15 at 10:09
12
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
  • \$\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 Nov 17 '15 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 Dec 5 '15 at 4:47

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.