![]() | ![]() |
|
Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum |
![]() |
| 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: |
![]() |
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... |
![]() |
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. |
![]() |
December 13th, 2007, 11:04 AM | #4 | |||
Joined: Dec 2007 Posts: 24 | Re: How do I randomly place an object on a map? Quote:
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 Quote:
Quote:
| |||
![]() |
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...)
|
![]() |
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.
|
![]() |
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.
|
![]() |
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 |
![]() |
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.
|
![]() |
August 3rd, 2009, 11:28 AM | #10 |
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, 10:19 PM | #11 | |
Joined: May 2012 Posts: 2 | Re: How do I randomly place an object on a map? Quote:
| |
![]() |
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
|
![]() |
![]() |
|
Tags |
map, object, place, randomly |
Thread Tools | |
Display Modes | |
|
![]() | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Object oriented design and the Observer pattern | milin | Programming | 2 | March 27th, 2018 11:48 PM |
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 |
Getting object-oriented programming right! | CRGreathouse | Programming | 4 | June 25th, 2008 10:24 AM |