What would be best solution for adding different sized objects to world?

Question

I am working on a game where I use different sized objects - such as houses, trees etc. My question is, which way should I determine is the place I am going to place my object free or not? World is generated randomly every time the game is launched.

(I'm only using x and z coordinates) For example, I have tree in a item pool with a size of 10x10, in the location 10, 0, 10 and I am going to add a stone which is size 5x5 for example. So how do I tell the stone "hey you can't place yourself to coordinates from 5 to 15 on x axis and 5 to 15 on z axis, place somewhere else".

Yes a simple way would be to just write down all the coordinates which are taken (5,6,7 ... 14,15), but what if I have 1000 trees? Is there any better and faster way to locate free spot for the item other than looping through a list of coordinates which have also looped to be written in taking a slot?

Answer 1

The logic behind hash-tables search can be inspiring.

To remind us of hash-table:

When searching for n in a hash-table

• we first look at h(n) where h is the hash function.
• Report the record if it hits, move to h(n)+1 if it misses.
• Report the record if it hits, move to h(n)-1 if it misses.
• Report the record if it hits, move to h(n)+2 if it misses.
• Report the record if it hits, move to h(n)-2 if it misses.
• Report the record if it hits, move to h(n)+4 if it misses.
• Report the record if it hits, move to h(n)-4 if it misses.
• ...

We set the step size to the numbers in 2^i sequence and their negatives (0,1,-1,2,-2,4,-4,8,-8,16,...)

---

Now in your scenario:

• we first look at t where t is the target location.
• Report the location if it's free, move to [t.x,t.y+1] if it's not.
• Report the location if it's free, move to [t.x,t.y-1] if it's not.
• ...
• Report the location if it's free, move to [t.x-1,t.y-1] if it's not.
• Report the location if it's free, move to [t.x,t.y+2] if it's not.
• ...
• Report the location if it's free, move to [t.x,t.y+4] if it's not.
• ...

Now how we tell if a location is free or not? You can create an actual hash-table to store all the objects positions in it. Now when you need to check for a free location around [x,y] to put a stone, you will have to search the hash-table for h(x,y).

If you need to place a bigger object like a 3x3 round-shaped fountain at location [x,y] you will need to check these records too: h(x+1,y), h(x-1,y), h(x,y+1), h(x,y-1). Since it's a round object you can approximate the area to simplify and thus remove four relative locations like h(x+1,y+1), h(x+1,y-1), h(x-1,y+1), h(x-1,y-1) from your search.

Afterwards you should add all these positions to the hash-table to make it easier to find occupied positions later on. e.g. adding a 3x3 object requires adding of 9 records to the hash-table.

Note that the hash function should reflect the two-(or three)dimensional world. e.g. h(x,y) = x*N + y where N is the max size of the world in y axis.

Answer 2

You could work with a grid system. Or to prevent objects from overlapping when placing them you could just add a collider to the object, set it as trigger and check if it collides with another object before placing it. If you want to keep some distance between objects you can make the colliders bigger.