Placing game entities in the scene at runtime


I want to let players place/build game objects on the scene. For example, build/buy a house or animal shelter and place it on the ground, or create a farm field (a 1x1 ground piece for growing plants) by hoeing the ground,…

Note, I am using JME heightmap terrain (TerraMonkey).

My requirements are:

  1. Game objects should be only placed on the flat areas that I have specified on the map. I need to figureout a way how to implement this.

  2. Game objects must not overlap with other objects when placing them on the ground. I want an area marker that indicates if an object can be placed there or not. An object might not be a physics object, so I can not make use of physics-based checks like sweep test,…

  3. Given a location on the ground I want to be able to check what object is over there. (2, and 3 basically refers to the same thing;)

I was thinking of doing a grid-based solution for placing game objects on the ground but I am interested to hear your opinion about this as well. Maybe there is a more flexible way to do this?

So the idea is that for specifying the areas on the map where objects can be placed I would generate a list of grid cells containing those areas. (For these areas I must make sure that terrain height perfectly matches the grid z)

And for each game object, I would need to generate a 2d grid-based bound. Not sure what should I call it. GridBound? GridShape? TileShape? VoxelShape?.. generally it is a list of cells in the XZ plane that an object is sitting on them. The list is serialized to a file on disk. I also need a GridShapeInfo component that links to the file name.

And an ObjectGridSystem that watches for entities with GridShapeInfo and Location component and generates a Map<Cell, EntityId> that maps a cell in the world into the entity that sitting on that cell.

Having the above info I can check whether a cell is available for placing an object or it is occupied by another object.

I am interested to hear your idea about this and know if there is a more simple way to do this.

Thanks in advance

Just note: once you’ve narrowed things down to half a dozen prospects, it’s not that big of a deal to just iterate over the objects and check them.

On the other side, if you make your grid cells too small then you end up managing millions of grid cells in the end for no good reason (see above).

Especially if these are axis-aligned objects, intersection is trivial for even hundreds of objects.

Edit: note that if you are trying to display some visual aid to the player with a detailed grid then that might be different… but even still, I’d personally just calculate that at runtime from existing broader phase style indexing (See above)

Yes, they are axis-aligned. Do you mean using bounding box checking?

Well for some game objects (like houses) using the bounding box checking I will lose some available spaces that can be used for placing stuff for example a well or garden,…

see the red hatched areas in the below house example:


Can you please elaborate more

Big grid, 32x32 cells say… bigger than any object. Objects are in a grid cell by their position. Whenever you want to check intersection with objects, you just load the 3x3 grid cells around your point and check those objects.

2D intersection testing (even non-axis aligned) is a “well solved problem” for any arbitrary shape, convex or not. Collision only gets particularly tricky in 3D. If things are axis-aligned then it’s often even easier.

Yes, but that object could be represented by smaller shapes or you could use more complicated (but trivially solvable) polygon intersection. If you don’t want to implement it yourself, Java2D already includes some polygon support that can be used in a pinch.

But now we get into the meat of things anyway because for odd shapes like this no doubt you will want sometimes when you can place some things the garden and other times you cannot. Maybe a tree is ok but another house is not… then you will want to not only know the shape of the house but all of the parts of that shape.

And at that point, breaking it into smaller parts makes a lot of sense.

You could even keep grids per shape if you want the simply approach but there is no need to index all of the objects this way.

If object bounds1 intersects object bounds 2 then check object grid cell overlap.