Metal Extractor placement

[Triaxx2]

AF has asked me to see if anyone knows how to make the computer choose where to place Metal Extractor's. At current, the engine can only give a yes or no if you can build there. Anyone have any idea's?

[Cheery]

Find the places which has relatively highest amount of metal(you have to blur the map), then make circular areas from that which tells which place would be the best to plant.

[munch]

AF has asked me to see if anyone knows how to make the computer choose where to place Metal Extractor's. At current, the engine can only give a yes or no if you can build there. Anyone have any idea's?

Quick and nasty (similar to how humans work): Use any old hill climbing algorithm to find the high points. E.g. see chapter 10 of numerical recipies (http://www.library.cornell.edu/nr/bookcpdf.html) and pick the one closest to you.

To do it half properly you'd need to know the distribution function that the mex uses when mining (i.e. presumbaly you mine more metal closer to the mex and less as you get further away), and integrate the product of it and the metal distribution on the map, to find out how much metal you'd get if you placed a mex there. You recalculate this for every metal spot in the vicnity to find the best one.

To do it for real, you need to plan several mexes at once. This is a bit tricky - it's a multidimensional problem. To keep it simple I'd pick a fixed number of mexes to start with. You then want to optimise their positions - I'd use either simulated annealing (again see chapter 10 of NR http://www.library.cornell.edu/nr/bookcpdf/c10-9.pdf) or a genetic algorithm. Or if that takes too long to calculate, for a quick and dirty method you could just try a fixed number of runs of a standard downhill algorithm (with random starting points) and pick the best result.

Either way the whole thing would be made much easier if there was a method in the Global API to let you ask the game "how much metal would I get if I put mexes in these positions" - failing that, perhaps you can rip the code out of the main program?

I hope this helps - it's probably clear as mud, in which case get back to me!

Cheers

Munch

[[K.B.] Napalm Cobra]

Concentrations about say 60% flag as metal spot, and prioritise them too.

[Doomweaver]

I think it mines equally everywhere within its radius.

[AF]

Napalm, what about maps where metal is uniformly distributed. Also what i meant is the extraction radius, there's no way fo finding the map data or any other thgin wihtout hardcoding a routine in that compared heightmaps whcih would balloon the dll to several hundred megabytes.

[[K.B.] Napalm Cobra]

Several hundred megabytes? What the hell are you on about?

[Triaxx2]

He means he doesn't want to have to list a massive amount of data in the form of a height map, which would cause the DLL to be much, much larger than is feasable.

[AF]

Lets say in the dll I held a copy of the heightmaps of every spring map ever made, just for the purposes of comparing them to the heightmap ingame ot get the name of the map.

That is what i meant.

[[K.B.] Napalm Cobra]

Thats retarded, you know now days you can load information from a file right?

[AF]

Which file. We havent got a map name or anything of the map save a metal map and a heightmap.

Also loading data from a file like that and comparing is mucyh slower than simply having a good metal extractor algorithm, which would be needed anyways even fi we did figure out the mapname.

[b1ind]

Although I don't fully understand the need for it, you could always compare the MD5 hashs.

[AF]

The point is to get the name of the map and its filename. Then we sue that top open the mapfile directly and get the value for metal extractor mining radius because ti isnt given to us in the engine interface.

[b1ind]

Seems to me that if such a hack would be necessary for something so crucial to an ai as extractor positioning, then there must be a flaw in the global ai interface. Wouldn't it be fairly trivial to add a method to retrieve a 'mapinfo' object (no idea what the actual class is). Then you could get the mapname from that for purposes of caching and you could also get the metal radius stuff. Might also be useful for future stuff that might take into account map hardness.

[AF]

methinks SJ has some xplainin todo.

[munch]

methinks SJ has some xplainin todo.

Oh come on 'tlantai, he's doing an amazing job and overlooked something fairly minor. You can still do mex placement, it just might be slightly non optimal that's all. Sure, it's a slightly broken API without the map info, but I think the explaining will probably be "I've been busy". Not that I know SJ at all, but I can tell he's busting a gut on this thing and I'm amazed at all the bases he's covering already. Let's give the guy a break.

Good to see you on the board again more by the way =)

Thanks for posting the Global AI =)

Munch

[SJ]

There is a GetMapName in the latest api courtesy of Zaphod.

[Kixxe]

Otherwise you could use data from the metal map and compare it... a pretty normal metal map is like, 500-1500 kbyte?

Or remake the metal map into TXT, and get the info there from. And for exctraktor radius, just let the AI get it from the .smd file and always place then so far from each other.

Offcourse, this would need a metal map (or a metal map positions in txt) for all maps... but it would work.

Also, in the txt, have some code for nearst unit distance / with metal value. Priortise close metal first, then more metal. And maybe some kind of defence ''outside'' the close metal.

hmm?

[AF]

kixxe that's all sorta obsolete now the callback interface has been updated.

oh well *updates cvs and recompiles*

[AF]

A few snippets from munch, who has gone on holiday. The foillowing findmetal() algorithm doesnt take account of the math involved with float3 structures and it also requires a position be passed itno it, which defeats the whole point of the algorithm. I need a metal extractor algorithm that returns a float3 co-ordinates being given only the unti ID of the metal extractor we want building and a pointer to a GlobalCallback class.

OK, so if you've got a 2D array of numbers representing the metal map, here's a really simple (but slow) algorithm to find the metal spot:

find_metal(position,
metal_array)
{
best_metal = metal_array[position];
new_postion = position;
improved = true;

while (improving)
{
improving = false
for delta = 1 move in each of the 8 directions (N,NE,E,SE,..,NW)
{
new_position = position + delta

while metal_array[new_position] > best_metal
{
position = new_position
new_position = position + delta
best_metal = metal_array[position]
improving = true
}
}
}

return new_position;
}

Since you won't need to run it very often, the lack of speed won't matter. In case it's not clear from the above, here's how it works:

You give it a starting point (e.g. where your comm/con unit is). It looks to see how much metal you would get from that point. Next it looks at the point directly above it ("North") to see if that point has better metal. If it does give more metal, then it keeps going North until it hits a point where going one step further North doesn't give any improvement. Then it tries going diagonally above and right ("North East"), and again if it finds an improvement carries on in that direction till there is no point going any further. The algorithm continues like this going round the compass points finding improvements, until eventually it finds a "maximum" i.e. a point which has higher metal than any of the points around it. That's where you want to put your mex.

There are a few problems with this algorithm:
1. is that it will only take account of existing mexes if you update the metal_array to reflect the mined area, which looking at your posts you don't know the radius of? - if you need an algorithm to update the metal array give me a shout
2. the algorithm only takes account of the value of the metal at the very centre point - it doesn't take account of the total value of metal mined. That means that if you run the algorithm several times from different start points and find several nearby metal spots, all you will know is which has the highest value at the centre, which may not in practice be as productive as a larger but lower value metal spot. Still this is very hard for a human player to judge correctly too.

Good news - I've figured out how to do it. First up, when you as a human player see the metal map on a new map for the first time you have no indication of the mining radius until you've placed your first mex (unless you know the map). OK, but you know how big the mex footprint is and you use that as a guess. So why not do the same with the AI? Instead of looking at the metal at a single point, you add up all the metal under the footprint of the mex. The question is, how big is the footprint of a mex? Hopefully you know the answer to this.

Anyway, here's the good bit: after you've placed your first mex there's a method in the Global AI to find out how much metal it's producing right? OK, well you can use that to work out what the mining radius is. Clever huh? The only thing missing from this picture is knowing how much metal a mex get's out of a given spot - somebody on the board said 60%, but that's easy to confirm we just look it up in the source code =)