Need system to track objects added to world in grid like way

My title is a little ambiguous but it was the most accurate I could muster lol.

So basically I am going to be adding objects to the world at integer world coordinates ie. 1m by 1m (height is irrelevant) boxes or 3m by 2m boxes at coords Vector3f(6, terrainHeight, 9). All I want is the x, z coords (y is up) and the y coord will be the height of the terrain. The world will be a set size currently 1024m by 1024m I want the user to add objects to the world (not in a mythruna type way, these objects aren’t becoming part of the terrain, they will be meshes like an rts type game, buildings etc). So I need to keep track of which spaces are occupied by objects to stop users placing two objects overlapping (objects cannot be placed with a corner at Vector3f(6.2f, terrainHeight, 8.89f). Something like a spreadsheet maybe could do this, however I doubt this is the best way to accomplish it.

Also bare in mind that the updates will need to be sync’ed across a network with other players.

So what would be a good way to accomplish this?


Uhm, just use a HashMap or something similar, you don’t need to store every empty “tile”, so just make a hash value of the x/y coordinates and then store an Object with the parameters you need (e.g. building type) in a HashMap. If you find something in the hash map for some location, then the space is occupied.

The way i see this is my head, might not come out right but ill try anyways xD. Exact implementation im not sure of either but, if you have some sort of 2d array, which corresponds to all the coordinates in your 1024x1024 world. Then when an object is placed, you update the array, either with booleans, or bit manipulation to save memory (dunno if its possible in java) and then send any updates across the network.

Arrays are not a good idea, rather think like database.get(x,y); than a huge array with mostly empty space, thats practically the definition of wasting space.

thats true

However though I want certain places that users cannot build in ie cannot build on the side of a mountain, or in water I need the terrain to be level enough etc… hmm I suppose I could just do this calculation on the fly on the server or users computer, I was hesitant that there would be a lot of wasted space if I tried to map all squares.

Well water would be at a certain height anyway so I could do it like this if block is at (1, 1) then check that height at (1, 1), (1, 2), (2, 1) and (2, 2) is all above water and also check that the difference between the highest and lowest point falls within a certain range then if so allow build and add to hashmap and for blocks bigger than 1m by 1m the process would be similar but only the origin would house the object and all other coords in the hashmap would be fillers so to speak, does this sound ok?

Also would it be a good idea to put all other objects in the scene into this system, trees etc to stop people building on the trees, rocks, non- user placed buildings etc… then the map init would have a hashmap already housing this data and users would just add to it.

If so I’ll get on with building it, thanks.

Well, for other stuff like base terrain height, you might want to have some algorithm that creates that for you and where you can ask like mySuperTerrainAlgo.getHeight(x,y); then you only need to store the tiles that have changed. Advantage is that you can have anything in mySuperTerrainAlgo, even an image/bitmap representation if that turns out to be the easiest way.

If storing the coords of the object as @normen is suggesting, make sure to allow for objects with an area larger than 1. So you will have to possibly store several points for one object. Also, you will have to maintain that mapping. If the object moves you will have to update the hashmap.

A simple solution, but possibly not the fastest, is to intersect the bbox of the item you are placing with the scene. If it intersects only the terrain, then you can place it. If it intersects something other than the terrain, it is blocked. You can then test the slope/height of the terrain at that location and see if it really is a good place to build.

Spatially organizing/indexing your objects will be important for performance in this case.