Map Grid Solver Needed

Map Grid Solver Needed

Discuss Lua based Spring scripts (LuaUI widgets, mission scripts, gaia scripts, mod-rules scripts, scripted keybindings, etc...)

Moderator: Moderators

Post Reply
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Map Grid Solver Needed

Post by Argh »

Ok, people, I am really close to finishing the first build of my little World Builder Gadget.

I've solved problems with AIs crashing (it was a gameframe issue- apparently AIs cannot deal, if the swap-outs occur during frame 0) ... I have random logic, replacing all of the Features on a map with Units... I've solved making the icons not draw on the minimap, they're stealth, they're reasonably fast, etc.

Now I "just" need to develop some logic that will allow for the creation of cities and other special features by game designers, either specific to their game in particular, or for Spring games in general (like, say, a city-generation algorithm that can be used with a "city" map type, giving us awesome city-fighting in Spring, with animated building collapses and other stuff, among other goals here).

I can see that I can get the locations of the Commanders on Frame 1 easily... so, I can exclude them, if I can figure out the whole issues of grids (more in a second). Looks like I can very easily use rectangular selection areas to deal with grabbing the new "features" and deleting them, to make room for things like cities, randomized forests based on some sort of algorithm, etc. All of this looks good.

Only problem is, I need an algorithm that will create and store a grid, so that I'm not just randomly destroying / creating over however many iterations I want this part of the logic to run, but am doing stuff that makes sense. To do this, I need to take the MapX / MapY, and store grid areas that have been already put to use, other than randomly, so that from then on, the script won't attempt to use them.

If you're not sure what I'm talking about, here's an example. This grid is totally blank, except for the player locations, ABCD:

XXXXXAXXXXXX
XXXXXXXXXXXB
CXXXXXXXXXXX
XXXXXXXXDXXX

We want to exclude those 4 locations from the first iteration, which builds a 2X2 box in our world, using building-set F. Ideally, we'd end up with something like this:

FFXXXAXXXXXX
FFXXXXXXXXXB
CXXXXXXXXXXX
XXXXXXXXDXXX

On the next iteration, we need to solve for available grid locations to place a 3X3 box, using building-set H. We cannot over-write ABCD or F, so we should see something like this:

FFXXXAXXHHHX
FFXXXXXXHHHB
CXXXXXXXHHHX
XXXXXXXXDXXX

On the next iteration, a 4X4 box is chosen at random. This has no solution on our map. It should not get placed at all, and the software should re-iterate, and mark down that 4X4 or larger is not possible, so that we don't waste CPU cycles trying to find a solution again.

See what I want? Pretty simplistic, really. But I really don't have a clue about how to go about solving this one- the data-storage requirements to store a 2D grid and use it to solve against are way beyond my meagre skills, and we already know that my ability to work with arrays is, well, terrible- I still don't really get it :P

It's the last major hurdle, folks, any ideas on how to solve this would be very, very useful- doing this randomly aside from start-positions is possible already, but I'd strongly prefer an iterative approach that solves this stuff more elegantly.

While I'm waiting for some responses, I'm going to start testing the part of this that will put in "unintelligent actors"- i.e., random collections of Units, both Neutral and non-Neutral, that will be assigned random patrol paths and wander around in groups- I've already done basic tests, as part of getting PURE's latest technical stuff done, and it's really pretty easy to do- we can have random Krogoths spawn every 20 minutes, for example, attacking all players ;)
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: Map Grid Solver Needed

Post by lurker »

I'm planning some code that performs some of these functions for the lua I'm writing right now. I'll talk more after I do some basic feasibility testing. But can you give me a rough idea of the size this grid will be? 20x20? 1000x1000?
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: Map Grid Solver Needed

Post by Argh »

Well, ideally, I'd like it to work from the heightmap grid (or 8X8 "elmos").

Then divide it down to more manageable chunks, for speedy iterations. Maybe 32X32 in Footprint scale, as the base size? I want to keep size as small as possible, so that the algorithms for a given set of Units can be kept in standard sizes and not bork, among other challenges. I also need to figure out a way, within the squares, for the resulting Units to be placed so that they have paths between them in most cases, so that pathfinding through these insta-cities is actually possible.

Ideally, really, really ideally- it'd be "smart" enough to deal with randomized rotations within a given solver-square, and handle them, so that we can have a lot of variety, but I'd be perfectly willing to settle for simplistic grids and then adjust the placement logic to produce results in the "good enough" category.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: Map Grid Solver Needed

Post by lurker »

Well, I started off planning to use this awesome thing I saw lua had. It's called userdata, and let's you allocate a chunk of ram and do whatever you want in it. I wanted to make a byte array to store the data.

except

You can only access userdata through the C api. :roll: So that leaves using a plain table, which will take roughly 13 bytes per entry. 13MB per 16x16 map area isn't horrible, but it's a heck of a lot more than 1MB...

I'll have a nice basic placement algorithm by Tuesday, if not today.

Argh wrote:I also need to figure out a way, within the squares, for the resulting Units to be placed so that they have paths between them in most cases, so that pathfinding through these insta-cities is actually possible.
Mark as used an area larger than what is placed?
Argh wrote:Ideally, really, really ideally- it'd be "smart" enough to deal with randomized rotations within a given solver-square, and handle them, so that we can have a lot of variety, but I'd be perfectly willing to settle for simplistic grids and then adjust the placement logic to produce results in the "good enough" category.
I have no idea what you mean.
Kloot
Spring Developer
Posts: 1867
Joined: 08 Oct 2006, 16:58

Re: Map Grid Solver Needed

Post by Kloot »

Sounds like you want to reimplement the blocking map in Lua. ;)
User avatar
AF
AI Developer
Posts: 20687
Joined: 14 Sep 2004, 11:32

Re: Map Grid Solver Needed

Post by AF »

In future never ever use diagrams written in text that aren't equations on a single line. You have an image editor, you should use it, using text doesn't help and for a lot of people can actually make things worse.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: Map Grid Solver Needed

Post by lurker »

Kloot wrote:Sounds like you want to reimplement the blocking map in Lua. ;)
In what I would be writing for Argh, the purpose is less blocking map and more the processing that's done on it to make random placement of large units faster. I don't know if it's worth it or not though...
But for my purposes the array has a very different use.
User avatar
AF
AI Developer
Posts: 20687
Joined: 14 Sep 2004, 11:32

Re: Map Grid Solver Needed

Post by AF »

Wouldn't the equivilant of ClosestBuildSite prevail in this situation?
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: Map Grid Solver Needed

Post by Argh »

I don't want to re-implement the blocking-map. Iterations must take place after replacement of trees and Geovent Features with new features (may cut the Geovent thing, since it's vital to many mods' gameplay interpretations of maps, but meh, it's not a biggie, just three lines of code). I dunno if, executing the same frame, the blocking map will be updated soon enough to make this happen. So, iterations will occur the next frame, to ensure that it works properly. Will almost certainly use the blocking map to find out what's already blocked, but I also want to remove all of the newly-created objects under that selection rectangle, so it's not as simple as that, really.

As for rotation issues, and a better diagram, let me get on that and I'll post something that's hopefully a little more helpful.
Post Reply

Return to “Lua Scripts”