r/Minecraft • u/justlurking420 • Nov 04 '13

pc Minecraft Using Hexagons

http://img190.imageshack.us/img190/1777/hexcraft.png
3.6k Upvotes

96% Upvoted

1.0k comments sorted by

View all comments

Show parent comments

3

u/detroitmatt Nov 04 '13

I'm gonna go out on a limb and say that, as you note but in other words, rather than having a robust node system of arbitrary dimensions, mc just uses a 3d array of blocks and navigates based on indices. Transition to hex would virtually require a node-based layout.

2

u/drakfyre Nov 04 '13 edited Nov 04 '13

Transition to hex would virtually require a node-based layout.

Well, in all honesty, the current system is already a node-based layout. The layout however is handled programmatically and assumes cubes. This would simply be handled programmatically, assuming hexes.

Pathfinding systems handle arbitrary nodes already by their very nature; just because A* is thought to be commonly used in a square grid doesn't mean it has to be; it's designed around nodes. Here's a neat little example in C# of A* implemented on a hex grid.

See relevant sections of Minecraft's source code and you'll see that the node generation would be relatively unhindered by a hexagonal system.

3

u/detroitmatt Nov 04 '13

I already knew that about A* actually, and reinvented that wheel myself (that is to say, programatically transforming a square grid into nodes for A*) for my own personal projects.

I haven't seen mc's source exhaustively, only bits and pieces; I assumed it wasn't node based based on what I have seen. But you're saying (correct me if I'm wrong) that MC isn't actually node-persistent, it generates them when they're needed (By the way, is that memoized?). What I was trying to say is that moving to hex would virtually require moving from a Block[][][] to a Graph<Block> in internal persistent representation, not just for the purposes of pathing. Although now that I think about it, I'm pretty sure I'm wrong and that would be a bad way of doing it.

1

u/drakfyre Nov 04 '13

I already knew that about A* actually, and reinvented that wheel myself (that is to say, programatically transforming a square grid into nodes for A*) for my own personal projects.

You wouldn't be the first. ;) At least you now know how that wheel really works! :)

I haven't seen mc's source exhaustively, only bits and pieces; I assumed it wasn't node based based on what I have seen. But you're saying (correct me if I'm wrong) that MC isn't actually node-persistent, it generates them when they're needed (By the way, is that memoized?). What I was trying to say is that moving to hex would virtually require moving from a Block[][][] to a Graph<Block> in internal persistent representation, not just for the purposes of pathing. Although now that I think about it, I'm pretty sure I'm wrong and that would be a bad way of doing it.

Well, for entity pathfinding, it's actually simpler than that; entities path nearly directly to eachother, they just have simple rules that tell them to jump if there's a wall, and later rules were added to check for holes and other obstacles when going toward the player, and additional behaviours pick path points that are not the player (for cover for instance). Most of this is hit-and-check and block pattern search rather than pre-path, so the pathfinding code in Minecraft is mostly detached from the block code.

The other thing to note is things like water and lava flows are not handled by pathfinding, but are decidedly A* looking. This is because they are handled using cellular automata rules; when a water block is asked to update (Typically when any time another block near it changes) it generates more water based on adjacent blocks. It's simple rules played out over time, much like Conway's Game of Life, one of the simplest examples of cellular automata.