How do I randomly place an object on a map?

Infinity · December 13th, 2007, 06:16 AM

I'm trying to work out an algorithm for placing an object on a map, based on already marked out zones where it can be placed. The difficulty is, the zones are of different sizes, where some zones might have 5000 pixels, and other zones might have 10 pixels or even just 1 pixel. I'm trying to invent a good way to place the object randomly so that it randomly switches around among the zones on a regular basis each time it is placed, with some bias to the larger zones. However, the larger zones are so much larger than the smaller zones that if I had the algorithm just randomly select a pixel where the object would be placed, it would almost always end up in the largest zone(s) and almost never would it be placed in a smaller zone. I am storing the data for the map in a two-dimensional array, with each pixel being marked as either possible for the object to be placed in or not possible for the object to be placed in. How can I write an algorithm to randomly place an object so that each time it is placed, it has a good chance if ending up in any particular zone, no matter how big it is, and how do I add a bias to the larger zones (in proportion to their size), without making the bias enormous?

As you can see in this example map, there are the white zones where the object can be placed, and the black areas where it can not be placed:

cknapp · December 13th, 2007, 07:56 AM

I would use a surjective (onto) function from the domain of a random number generator onto the pixels that are acceptable. Granted, this would be hard to not kludge.

Another option, albeit a sketchy one is to randomly do a new test if it lands on the large area. This would weight it toward the smaller regions, but you could be rolling dice for about an eternity (actually, not eternity, since pseudo-random generators loop, but...)

I really think some sort of weighted function would be best...

CRGreathouse · December 13th, 2007, 09:03 AM

How do you store the areas, and how much do you want to bias the selection toward small islands?

You mentioned the first obvious method: generate a random point, regenerating ones that don't land on an island. This method selects islands with probability equal to their land share.

Another method would be to store a list of islands and select one randomly, then choose a point from it.* This obviously selects islands with equal probability.

If you need user-defined bias, a linear combination of the two would be possible. Let the user set 0 <= bias <= 1, select a p uniformly on [0, 1), and if p < bias use the second method; otherwise use the first.

If you instead have a good idea of how much bias you want, there are surely methods that could be faster. How sparse is your representation?

* There are various ways to make this more efficient than it sounds, if need be.

Infinity · December 13th, 2007, 10:04 AM

Quote:

How do you store the areas, and how much do you want to bias the selection toward small islands?

Basically, the map is stored in a text file by marking down the beginning and ending pixels of any white area in a given horizontal line of pixels across the image. The file writer I made looks at the black and white map line by line, and within each line it travels along the line pixel by pixel, marking down any pixel coordinates that are the first and last white pixels in any line of white pixels it finds on the line of pixels it is considering. If it is a lone white pixel, then the beginning and ending pixels marked down are the same.

An example of a text map file: Only those lines which have any white pixels on them are written into the file, hence the reason that it starts on line 2:

Code:

2: 2,336 
3: 2,336 
4: 2,337 
5: 2,338 
6: 2,339 
7: 2,340 
8: 2,341 
9: 2,342 
10: 2,343 
11: 2,344 
12: 2,345 
13: 2,346 
14: 2,348 
15: 2,349 487,496 
16: 2,351 486,496 
17: 2,352 485,496 
18: 2,353 484,497 
19: 2,355 482,497 
20: 2,356 474,499 
21: 2,358 474,500 596,605 
22: 2,359 468,500 596,608 
23: 2,360 467,500 596,609 
24: 2,361 467,502 596,610 
25: 2,362 368,373 466,502 596,611 
26: 2,362 367,374 465,503 593,612 
27: 2,363 366,375 464,507 592,614 
28: 2,363 365,376 464,507 591,615

Now, of course, applying the reverse of this file-writing compression algorithm that I used could easily be used to either reconstitute the map from the text file, or to write a two-dimensional array such that the indexes of the array matches the pixel indexes of the original image, and either 'white' or 'black' was stored in each array cell representing its corresponding pixel on the map. Thus, a version of the map could be stored in memory that the computer could understand and use.

Quote:

I really think some sort of weighted function would be best...

Quote:

Another method would be to store a list of islands and select one randomly, then choose a point from it.

It sounds like a combination of these two ideas might do the trick, if we can work out the details. If we had a list of the islands and their respective sizes, we could just have it randomly pick an island, weighted by its size, and we could also easily adjust the weighting algorithm if we wanted to without any problems. Then a point from that island would be randomly picked. But how would the computer know how many islands were in the map, and what sizes they were, just based on the map data in the text file or the array in memory? I think that's the big problem right now. If I could get an algorithm that could look at either of those and generate how many islands were on the map and how many pixels were in each island, I think I'd be in business from there.

cknapp · December 13th, 2007, 10:20 AM

Any adjacent "white" pixels will be on the same island. Finding if two pixels are adjacent is rather easy. Deciding how to store it might be tricky. But an obvious way (not necessarily a good way) is to store all the locations on each island in an array, and storing each one of these arrays in an array. (I told you it wasn't necessarily good...)

Infinity · December 13th, 2007, 02:07 PM

Actually, that's a pretty good idea, because I would only need the arrays you mention to set up the objects on the map, and then the arrays could just be deleted from memory, clearing the space. In other words, it really doesn't have to be super-efficient, as long as it's decently workable, it should function well.

CRGreathouse · December 13th, 2007, 08:15 PM

Yes, a precomputed table of islands would be the way to go then. Add each different block in first line as its own island, noting its size and at least one point on it. For each further scan line, see if it connects to a pixel above (if so, mark it as on that island). If it's a part of more than one, combine the two and their respective sizes. Continue until you have all the lines and some collection of islands. Defrag here if needed (depending on how you store the data, you may have 'holes') and do your stuff.

SidT · June 11th, 2009, 01:35 PM

In Visual Basic 2005:

Code:

    Public Function GetRandPointOnMap(ByVal image As Drawing.Bitmap) As Point
        Dim x As Integer = image.Width
        Dim y As Integer = image.Height
Start:
        Dim randx As Integer
        Dim randy As Integer
        Dim generator As New Random
        randx = generator.Next(0, x)
        randy = generator.Next(0, y)
        If image.GetPixel(randx, randy) = Color.White Then
            GoTo NextThing
        Else
            GoTo Start
        End If
NextThing:
        Return New Point(randx, randy)
    End Function

But you could be waiting a very long time before a value appears.

daveD · June 11th, 2009, 11:09 PM

I really would like to say thanks to all for sharing very informative views here.

julien · August 3rd, 2009, 10:28 AM

Out of curiosity, in which context were you trying to generate random points on these regions of your screen ?

monica · May 7th, 2012, 09:19 PM

Quote:

Originally Posted by cknapp

I would use a surjective (onto) function from the domain of a random number generator onto the pixels that are acceptable. Granted, this would be hard to not kludge.

Another option, albeit a sketchy one is to randomly do a new test if it lands on the large area. This would weight it toward the smaller regions, but you could be rolling dice for about an eternity (actually, not eternity, since pseudo-random generators loop, but...)

I really think some sort of weighted function would be best...

monica · May 7th, 2012, 09:21 PM

it must be placed at the fixed location

December 13th, 2007, 07:56 AM	#2
cknapp Joined: Dec 2007 Posts: 138	Re: How do I randomly place an object on a map? I would use a surjective (onto) function from the domain of a random number generator onto the pixels that are acceptable. Granted, this would be hard to not kludge. Another option, albeit a sketchy one is to randomly do a new test if it lands on the large area. This would weight it toward the smaller regions, but you could be rolling dice for about an eternity (actually, not eternity, since pseudo-random generators loop, but...) I really think some sort of weighted function would be best...

December 13th, 2007, 09:03 AM	#3
CRGreathouse Joined: Dec 2007 Posts: 232	Re: How do I randomly place an object on a map? How do you store the areas, and how much do you want to bias the selection toward small islands? You mentioned the first obvious method: generate a random point, regenerating ones that don't land on an island. This method selects islands with probability equal to their land share. Another method would be to store a list of islands and select one randomly, then choose a point from it.* This obviously selects islands with equal probability. If you need user-defined bias, a linear combination of the two would be possible. Let the user set 0 <= bias <= 1, select a p uniformly on [0, 1), and if p < bias use the second method; otherwise use the first. If you instead have a good idea of how much bias you want, there are surely methods that could be faster. How sparse is your representation? * There are various ways to make this more efficient than it sounds, if need be.

December 13th, 2007, 10:20 AM	#5
cknapp Joined: Dec 2007 Posts: 138	Re: How do I randomly place an object on a map? Any adjacent "white" pixels will be on the same island. Finding if two pixels are adjacent is rather easy. Deciding how to store it might be tricky. But an obvious way (not necessarily a good way) is to store all the locations on each island in an array, and storing each one of these arrays in an array. (I told you it wasn't necessarily good...)

December 13th, 2007, 02:07 PM	#6
Infinity Joined: Dec 2007 Posts: 24	Re: How do I randomly place an object on a map? Actually, that's a pretty good idea, because I would only need the arrays you mention to set up the objects on the map, and then the arrays could just be deleted from memory, clearing the space. In other words, it really doesn't have to be super-efficient, as long as it's decently workable, it should function well.

December 13th, 2007, 08:15 PM	#7
CRGreathouse Joined: Dec 2007 Posts: 232	Re: How do I randomly place an object on a map? Yes, a precomputed table of islands would be the way to go then. Add each different block in first line as its own island, noting its size and at least one point on it. For each further scan line, see if it connects to a pixel above (if so, mark it as on that island). If it's a part of more than one, combine the two and their respective sizes. Continue until you have all the lines and some collection of islands. Defrag here if needed (depending on how you store the data, you may have 'holes') and do your stuff.

June 11th, 2009, 11:09 PM	#9
daveD Joined: Jun 2009 Posts: 21	Re: How do I randomly place an object on a map? I really would like to say thanks to all for sharing very informative views here.

August 3rd, 2009, 10:28 AM	#10
julien Site Founder Joined: Dec 2007 Posts: 414	Re: How do I randomly place an object on a map? Out of curiosity, in which context were you trying to generate random points on these regions of your screen ?

May 7th, 2012, 09:21 PM	#12
monica Joined: May 2012 Posts: 2	Re: How do I randomly place an object on a map? it must be placed at the fixed location

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Object oriented design and the Observer pattern	milin	Programming	2	March 27th, 2018 10:48 PM
Practicing Object-Oriented programming	julien	Programming	0	March 16th, 2013 03:42 AM
Best place to learn HTML5 and CSS3	shyronnie	Web Design	2	June 21st, 2012 11:59 PM
Getting object-oriented programming right!	CRGreathouse	Programming	4	June 25th, 2008 09:24 AM