JohnCake JohnCake - 3 months ago 13
Java Question

Most efficient way to run tests against this stored data

Sorry for the not too informative title, I couldn't think of anything better. When I say efficient I mean code that isn't cpu intensive.

Problem:
Imagine a 3D spaceship made out of blocks, like one build in minecraft. I want to store the location of every single block in this shapeship in a self-made Ship class.

For this I was using

private List<ShipBlock> shipBlocks;
inside the Ship class. ShipBlock here is a self-made class, which holds a position in the form of a vector
Vec3(int x, int y, int z)
as well as some other information irrelevant to this question.

But now I want to perform a test on the ship. Wether the ship contains a ShipBlock on a certain testPosition (x, y, z), and if so return the ShipBlock for this. I have however not found a way to do this efficiently. Looping through the entire List and to test every position against the testposition is pretty expensive and I'd like for it to be fast.

So instead, I decided to make a
Map<Vec3, ShipBlock> shipBlocksMap
to store the information. Where the key would be the ShipBlock's position. I could simply do
shipBlocksMap.get(testPosition)
and it would return the correct ShipBlock if the ship has a ShipBlock in that position. If not it would return null.

It seemed to be exactly what I wanted, untill I moved the ship and all ShipBlock's got new positions. I learned here that key's in a map don't change if the object you gave as a key changes. And thus if I now were to use
shipBlocksMap.get(testPosition)
using a position that is in the moved ship, it would return null as the key's are still the old positions. (Sorry if it's confusing, I'm not sure how to explain it better)

Question:
The question that I'm asking here is: Say if the ship can contain tens of thousands of ShipBlocks, what is the most efficient way to test if it contains a ShipBlock with a certain position. And in what way should I store the ship's ShipBlocks so this check goes efficiently?

Code:
Incase anyone wants to see it here is the code to the Ship and the ShipBlock classes.

public class ShipBlock
{
public Vec3 position;
public String shipBlockType;

public ShipBlock(Vec3 position, String shipBlockType)
{
this.position= position;
this.shipBlockType = shipBlockType;
}
}

public class Ship
{
private Map<Vec3, ShipBlock> shipBlocksMap;

public Ship(Map<Vec3, ShipBlock> shipBlocksMap)
{
this.shipBlocksMap = shipBlocksMap;
}

public ShipBlock containsShipBlock(Vec3 position)
{
return shipBlocksMap.get(position);
}
}

Answer

I think the most important design change is to save the blocks' positions relative to the ship's position.

This way, you do not need to change the keys of the blocks when the ship moves, and can easily use your Map<Vec3, ShipBlock> shipBlocksMap for a constant-time test, where the keys are then the relative positions. You can get the relative position by computing (conceptually) relative_block_pos = absolute_block_pos - ship_pos.

That means you need to store the position of the ship. As one option, you may to simply choose the first block of a ship as the ship's position, thus the first block always has coordinates (0, 0, 0).

This way, changing the coordinates of all blocks is reduced to a minimum (but should be not required in most cases).

Comments