13 hours ago, pathfinding said:

I still don't understand how that stores a coord pair of {x:1, y:2, z:3}. Could you show an example using those?

For each of the three forms? (You didn't say which one.)

Assumptions: width=6000, height=6000, maxz=4 (I always start counting at 0 rather than 1, so max is always one bigger than the biggest allowed value). Otherwise, I am just filling in the constant 'width' and 'height' values at the spots where it says 'width' or 'height', in the text I explained before.

For D[x + y * width + z * (width*height)], D is an array like D = new Tile[6000 * 6000 * 4]; // width * height * maxz

(x=1, y=2, z=3) can be found at D[1+ 2 * 6000 + 3 * 6000 * 6000];

For the increase or decrease in y for z, D is an array like D = new Tile[6000][4*6000]; // [width][maxz * height]

(x=1, y=2, z=3) can be found at D[x][y + 6000 * z] = D[1][2 + 6000 * 3];

For the stair jump table, there is no z, only x and y. Think of it as 3 separate buildings, 1 floor high, standing right next to each other. Your x/y coordinates spans all three buildings. Each building is a "z" level. You cannot leave or enter a building without teleporting, so your reachable x/y coordinates are limited if you only walk 'horizontally'. You can however teleport between buildings, so you land in a different set of x/y coordinates that you can reach.

For example, you could have one building between (0, 0)--(3000, 300), the second building between (3001, 0)--(6000, 3000), and the 3rd building between (0, 3001)--(6000, 6000). So if you're at (4563, 123), you're in building 2, or "floor" 2. If you teleport to (77, 5931), you teleported to building 3 (aka floor 3).

Of course, in the latter case you don't need to have the same shape at every floor or have equally big amounts of space for each floor. It's much more flexible.

7 hours ago, Alberth said:

For each of the three forms? (You didn't say which one.)

Assumptions: width=6000, height=6000, maxz=4 (I always start counting at 0 rather than 1, so max is always one bigger than the biggest allowed value). Otherwise, I am just filling in the constant 'width' and 'height' values at the spots where it says 'width' or 'height', in the text I explained before...........

Doesn't this seem more complicated than just using three separate array indexes? int[z][x][y] = new int[3][6000][6000]; seems way more straightforward and would end up being the same amount of tiles anyway. Why not just use this instead?

5 hours ago, pathfinding said:

Doesn't this seem more complicated than just using three separate array indexes? int[z][x][y] = new int[3][6000][6000]; seems way more straightforward and would end up being the same amount of tiles anyway. Why not just use this instead?

You asked how to store a 3d map in a 2d plane. I just answered that question.

I think the main point to take away is that what the player thinks and sees can be different from what the code is actually doing. As long as you keep the illusion complete, he/she will believe anything you say.

As to why, there can be technical reasons why one form is more preferred than another form. If you have a large 1D array like my first solution, "position" becomes a single number, rather than 3 numbers, which can be an advantage in coding.

You say not all tiles will be reachable. That means you're currently wasting memory space while storing the map, the 3d array does have space for the full amount of tiles even if you don't use them. Depending on how irregular your map is, such waste may become significant enough to fix.

16 hours ago, pathfinding said:

Doesn't this seem more complicated than just using three separate array indexes? int[z][x][y] = new int[3][6000][6000]; seems way more straightforward and would end up being the same amount of tiles anyway. Why not just use this instead?

You're better off creating different 2D planes all together and representing them as "levels", and saving/loading each level to/from your db. When the player decides to go down some stairs, they load a level, instead of changing their z-position. 

What you are doing with the 3 coordinate system is not performant at all, and you'd have to implement this as a 2D array anyway, unless your game camera essentially turns off the top layer rendering, current monsters, collision, and everything else just to go down one layer to turn all of the bottom layer rendering, monsters, collision, and everything else on.

@Alberth

Thank you for explaining how to do so, I really appreciate it.

@Alberth @conditi0n

Wouldn't a HashSet work just as well? No memory loss if I just store a new Tile(1, 2, 3) and have the hashCode() generate on (x, y, z), then store it in a HashSet? I feel like there's nothing more optimal than this, or is there? The HashSet would only store the exact number of tiles generated, no extra spaces in memory (like the array). A lookup would be extremely fast too...

set.add(new Tile(1, 2, 3));

set.contains(new Tile(1, 2, 3)); // Returns true

Without more complex wrapping code, that HashMap technique leaves no ability to store data relevant to that tile, other than its coordinates.

If the only information you have, or will ever need, about a tile is whether or not it is walkable, why aren't you just using a X*Y*Z BitSet, which consumes 1 byte per 8 tiles of walkable data?

12 hours ago, pathfinding said:

Wouldn't a HashSet work just as well? No memory loss if I just store a new Tile(1, 2, 3) and have the hashCode() generate on (x, y, z), then store it in a HashSet? I feel like there's nothing more optimal than this, or is there? The HashSet would only store the exact number of tiles generated, no extra spaces in memory (like the array). A lookup would be extremely fast too...

HashSet would work. Indeed it doesn't provide storage for positions that you don't have, on the other hand, internal book-keeping of a hash table isn't free either. https://en.wikipedia.org/wiki/Hash_table has a lot of details. The load factor there may be killing your advantage (75% load factor is around 25% free entries, ie (= about 3*6000*6000/4 free for a full map)). In general, arrays are extremely fast to access if you have a simple incrementing integer value that you can use for indexing (which you have with positions).

One question you may want to consider is whether you need all 3 floors loaded, or even, do you need the entire floor? 3*36M tiles is nearly 100M tiles. If 1 tile is 64 byte (which you have soon), it's 6,4GB memory that you need, not counting any overhead to organize the tiles in 3 floors.

For a big map it can be beneficial to divide the grid in chunks. Because it can limit the amount of pathfinding iterations. The suggestion of Wyrframe seems fine, including placing additional portals to divide the map, but it sounds less flexible. Depends on the number of open areas and maps you are about to make.

If you just divide the map in a regular grid and pre-calculate the connection between each chunk then you end up with a small network which serves as the first pass of your pathfinding, this one will be super fast. For example this is like navigating over which countries you travel on a world trip. You could even enhance this and consider the shortest distance (From A to C over B) in the pre-calculation process.
Here is why that could be interesting:

Next you can calculate the exact path by only using the tiles which belong to these chunks.

Here is an example of something similar in action: https://www.youtube.com/watch?v=RMBQn_sg7DA
 

On 5/22/2019 at 9:37 AM, pathfinding said:

@Alberth

Thank you for explaining how to do so, I really appreciate it.

 

@Alberth @conditi0n

Wouldn't a HashSet work just as well? No memory loss if I just store a new Tile(1, 2, 3) and have the hashCode() generate on (x, y, z), then store it in a HashSet? I feel like there's nothing more optimal than this, or is there? The HashSet would only store the exact number of tiles generated, no extra spaces in memory (like the array). A lookup would be extremely fast too...

set.add(new Tile(1, 2, 3));

set.contains(new Tile(1, 2, 3)); // Returns true

 

Are you referring to walkable areas/non-walkable areas within world space? certainly. you can store every walkable tile as an index in a hash table. or, you can create a navigation mesh out of a collection of tiles and assume they're walkable, then store them all in a hash table (which might be a bit harder to do - a graph might be better for this).

my point is that, to render these things, using a 2d camera system, and to calculate collision, and do calculations of the entities that are "upstairs" or "downstairs", and calculate whatever other procedural elements you have in your world. you are not going to want to create several height-layers to such a large world without custom culling code that has to remove the other layers, when you can simply remove them yourself using a level system.