Finding enough space

ID:152139
 
Jan 4 2008, 11:30 pm (Edited on Jan 4 2008, 11:46 pm)
For pif_MapLoader 3.0 I'm adding the ability to find space for a map on an area that already exists. By this, I mean searching for a "clear" area on the existing area. I'll be doing this by passing types that can be written over as arguments to the function. I already had this in pif_MapLoader 2.0, but it was terribly inefficient. Does anyone have any ideas on an efficient way to do this?

PS: If you need a visual aid to get what I mean, ask. I'll work one out.
Jan 4 2008, 11:57 pm
I think I get what your saying.

An example would be you have a few cities thrown about, but the grasslands in between would be blank space waiting for a new city (or whatever) to be built?


((By the way, I am really looking forward to 3.0 ^.^))
Jan 4 2008, 11:58 pm
In response to Jamesburrow
Yea. Another use I can think of is if you had a random map generator, and wanted to load a template of a shrine or cave or something somewhere where no trees or rocks or anything are.
Jan 5 2008, 12:03 am
In response to Popisfizzy
Ah, ok. I thought so.

As for your efficiency question, I'll have to think on it. There is a way nagging at the back of my head, but I'm not quite sure how to phrase it (or if its even possible... heh)
Jan 5 2008, 4:29 am
Well, one way to do this is seperate the map to chunks of the size of the template loaded, and check each of these chunks to see if the template can be loaded in there. If you want to optimize this a bit, you could list together templates of the same size that require the same conditions to be loaded, so you'd only need to check the map once for each of those. Here's some psuedo-code:

// when the world is created:
for map in maps
    new_maps["[map.size]-[map.conditions]"] += map
maps = new_maps

// to check:
minx = 1
miny = 1
step_x = loaded_maps.size_x // loaded_maps is a datum containing common attributes for all associated maps in maps["[some_size]-[some_conditions]"]
step_y = loaded_maps.size_y
for maxy in step_y to world.maxy step step_y
    for maxx in step_x to world.maxx step step_x
        block = block(locate(minx,maxx,z),locate(miny,maxy,z))
        // check [block] for availability and do stuff
        minx = maxx
    miny = maxy


It probably won't be very fast for large locations (or small templates), but it's the only method that comes to mind.

PS. I hope this is what you meant!
Jan 5 2008, 6:26 am
In response to DivineO'peanut
I had thought about that, but quickly dismissed that method when I delved deeper into it. It's is entirely possible, and extremely probable, that spaces will be spread out across the section. As, for a large majority of maps, the number of disordered sections vastly outnumbers the ordered sections, it's actually rather unlikely that the space will actually be one of the ordered areas.
Jan 5 2008, 9:26 am
Without containing any database of chunks and such, I can only think of some pretty inefficient methods. I guess the best idea when you load a chunk of map is to just add that to a new z-layer and work from there. It'd be completely blank and you can record the chunks of the map used and their exact dimensions, so then you know where to check.
Jan 5 2008, 10:03 am
In response to Popisfizzy
Regretfully, I don't think there's a better way to do this without a premade database. You can make the algorithm a bit faster after the first time it is used by storing available chunks and removing them when they're used, but then it won't be very useful because you'd have to account for map updates all the time.

Aug 5 2008, 8:04 am