1
\$\begingroup\$

I have been trying to implement pathfinding in Minecraft for a while. Everything is in blocks, so this shouldn't be too difficult. I have gone through a lot of different posts and articles but I haven't seen any actual implementation for A* pathfinding in Java. I can't find any libraries that can help me with this either. Many existing solutions use a grid implementation for their pathfinding. For example, using the Slick2D library, I would implement 2D pathfinding using the following:

1 -> Transform the area around the player into a grid of 1 and 0, where 0 is walkable and 1 is not. This seems pretty inefficient.

2-> Run the pathfinding on this grid.

This is not what I want, as this is very inefficient. How would I go about actually coding pathfinding that does the following:

1: Interacts directly with the Minecraft world, so I wouldn't have to keep generating a grid that can be used with libraries.

2: It has to be 3D, as in it could navigate terrain that isn't flat.

Thank you very much for the help! I am not asking for code, but I just want to know how I would go about this.

Have a great day :)

\$\endgroup\$
6
\$\begingroup\$

What A* needs to work is the following:

  • Given the current node, get the list of possible nodes it can move to, with their costs.
  • The ability to evaluate the heuristic function.

Please notice I've said nothing of a grid. A* will work with any graph, with nodes and links. If you could have the graph pre-made, you would just execute on the graph. But you don't have to. So, instead of having links, we will have a function that give you the neighbors of a node.


For your case, of course, the nodes would be the cubes/blocks/cells/voxels of the world. And you will have reference to them. Given that we are talking Java, perhaps you have a reference type for the nodes. Alternatively, you have them in some indexed data structures, and you can reference them by that index (the index could be the 3D coordinates, for example).

So, you will have a function that takes a reference to a block, and gives you a array/list/iterable of the references to the blocks the character can move into. Considering whatever mobility options are available (e.g. walking, jumping, swimming, and so on). Those would be the links.

You would do that by querying the neighbor blocks to the given one, checking what are they of, and determining whatever or not the character could move there.

However, you also need the costs. You probably are better off computing that at the same time, in which case you would not return references to blocks, but pairs of references to blocks and costs. Another option is to have a function that will take references to two neighbor blocks, and tell you the cost.

What is the cost? Well, presumably it consider mobility options and terrain type. For example: walking over mud costing more than walking over stone (that is, the character walks faster/easier on stone than on mud), or for example jumping costs more than walking. And if you can't go there, you can say cost is infinite.

Note: You could have a pre-computed graph with all information, perhaps update it when a block changes, and execute A* there. In fact, you could store store that in the same structure in memory that has the blocks (so each block would know how much it cost to move from it to its neighbor blocks).


And of course, you need the heuristic function is an estimate of the cost to get to the goal. Presumably you would start by the distance in strighline to the goal, perhaps add extra cost for verticality (i.e. if getting there must require at least x jumps, and each jump costs z more that walking, add x*z extra to the heuristic).


Now, you can implement A*. Go find the pseudocode somewhere. For example: A* pseudocode on wikipedia. Or try Rosetta stone. I will also advise to read about some variants and optimizations. In particular Iterative Deepening A* and Memory bounded A*.

I suppose you will have to modify the code anyway. And thus I should advocate for you to understand it. And for that, I think you should start by understanding Dijkstra's Algorithm. I'll let Computerphile help with that:


Addendum: See also Amit Patel's Introduction to the A* Algorithm at Red Blob Games.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much for this great detailed answer! This really cleared things up for me. I will try what you have suggested! Also, by the way, thanks for the wiki page. This has helped me a lot. Have an awesome evening! \$\endgroup\$
    – Day Trip
    Nov 18 '21 at 0:37
1
\$\begingroup\$

The same way you do for a 2D world (or flat 3D world). The only differences would be the cost calculation and movement possible to get to neighbors.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .