Search code examples
unity-game-engineoptimizationlocationcoordinategenerate

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

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?

Solution

  • 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.