Jump to content
  • Advertisement
Sign in to follow this  
epistax2

How to (randomly) fill a space with objects?

This topic is 2496 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In a game-map description I have an area called a 'spawn zone'. Objects are allowed to spawn within this area. The tricky part I am running into is setting up a somewhat deterministic system for creating objects in seemingly random locations inside this zone.

Now in the grand scheme of things, this problem is actually an NP complete one. I'm just looking for a good-enough solution.

The current horrible implementation I have is to pick a random spot in the spawn zone, and determine if there is room for a new object. If not, repeat. This solution probably puts me in the realm of an O(n^2) operation at best because for each object already in the spawnable area, there's a chance to hit it. This isn't good enough in my case because of the timing, and also the inability to check for a unsolvable case. One too many objects to be spawned may just happen to create an impossible problem depending on how the randomly placed objects appear. (If anyone needs a picture I'll be happy to add one)

Now I had an idea but I haven't developed it mentally yet. It comes down to subdividing the spawn zone prior to spawning any objects. This would be easiest if (a) I knew how many objects needed to be spawned up front and (b) I knew how big each object would be. Before I went off the deep end here I was curious if there was already a known best practice.

Thanks for reading. I eagerly await the ideas of the masses!

Share this post


Link to post
Share on other sites
Advertisement
How about:
- subdivide the zone
- randomly shuffle an array of pointers to subdivisions
- randomly place a single object in each of the first N subdivisions according to this now-shuffled array

Share this post


Link to post
Share on other sites
Subdivision works best, I have exactly the same problem in the game I'm developing now. Now lets split your problem into two parts.

1. Deterministic - Indeed, if you want to have a somehow even distribution of your spawned items in the map, you need to split it by areas, and then make a uniform distribution of objects in each area (i call them chunks) - exactly as TheUnbeliever said.

2. Performance - Subdivision of the area will improve the issue a bit because you are basically splitting the total number of items you have to check against when you spawn a new one. However, the key here is the ratio between the number of items to be generated and the space available. If the items are sparse it works OK, but if you have a high density, you can get into serious trouble.

In my case, I have a low item density, so it works very fast. However, I don't have to do spawning in real time. I generate the items on level creation and hide them, only to show them at the right time to the player. This has 0 performance hit during game running, but even this solution can't help you if you have a high items/space ratio, as it can generate virtually infinite generation times.

There is a solution for generating this but it would require some more memory and some computational overhead in managing it. What you would need to do is to store all your "availabile locations" into some data structure. Each time you generate an item, you randomly pick an available location from your data structure, then you remove that location from your available locations. This way you ensure that no collision between new items and existing items would happen. However, the memory and finding-removing items from this data structure might not be worthy if your items density is low.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!