My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
December 13th, 2007, 07:16 AM   #1
 
Joined: Dec 2007
Posts: 24
How do I randomly place an object on a map?

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:
Attached Images
File Type: gif example.GIF (1.3 KB, 2551 views)
Infinity is offline  
 

My Computer Forum is free to register and we welcome everyone!

December 13th, 2007, 08:56 AM   #2
 
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...
cknapp is offline  
December 13th, 2007, 10:03 AM   #3
 
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.
CRGreathouse is offline  
December 13th, 2007, 11:04 AM   #4
 
Joined: Dec 2007
Posts: 24
Re: How do I randomly place an object on a map?

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.
Infinity is offline  
December 13th, 2007, 11:20 AM   #5
 
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...)
cknapp is offline  
December 13th, 2007, 03:07 PM   #6
 
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.
Infinity is offline  
December 13th, 2007, 09:15 PM   #7
 
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.
CRGreathouse is offline  
June 11th, 2009, 02:35 PM   #8
 
Joined: Dec 2008
Posts: 30
Re: How do I randomly place an object on a map?

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.
SidT is offline  
June 12th, 2009, 12:09 AM   #9
 
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.
daveD is offline  
August 3rd, 2009, 11:28 AM   #10
Site Founder
 
julien's Avatar
 
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 ?
julien is offline  
May 7th, 2012, 10:19 PM   #11
 
Joined: May 2012
Posts: 2
Re: How do I randomly place an object on a map?

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 is offline  
May 7th, 2012, 10:21 PM   #12
 
Joined: May 2012
Posts: 2
Re: How do I randomly place an object on a map?

it must be placed at the fixed location
monica is offline  
Reply

  My Computer Forum > Computer Science Forum > Algorithms

Tags
map, object, place, randomly



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Practicing Object-Oriented programming julien Programming 0 March 16th, 2013 04:42 AM
Best place to learn HTML5 and CSS3 shyronnie Web Design 2 June 22nd, 2012 12:59 AM
Object oriented design and the Observer pattern milin Programming 1 January 10th, 2009 07:16 PM
Getting object-oriented programming right! CRGreathouse Programming 4 June 25th, 2008 10:24 AM





Copyright © 2018 My Computer Forum Forum. All rights reserved.