Page 2 of 3
Posted: 24 Jul 2005, 12:26
by Triaxx2
Hey, why not treat the metal map, as a seperate map? Give it a height map, and build/no build restrictions, but include in no build, places within a certain distance of the edge of the metal spread. The distance would be just slightly smaller than the mex's range of extraction.
Posted: 24 Jul 2005, 13:29
by AF
You mean run the building placement algorithm through the metal map instead of build/nobuild?
But then wont I get metal extractors placed ontop of my patches next to eachother mining the same area. And then what do I term as buildable and not buildable? But it does have some merit. Perhaps if we could get the extraction radius of the map first though.
Or maybe an is the map being mined at this point? function. That way it'd be much easier to use the placement algorithm.
Posted: 24 Jul 2005, 20:05
by AF
taken from unitdef.h, UnitDef* ued = callback->GetUnitDef(58); ued->extractrange;
Posted: 24 Jul 2005, 23:52
by Triaxx2
Sort of the idea is, to have the extractors aiming only for areas where there is metal. While they can have over lapping extraction areas, they won't build inside the areas of others, so you don't get four, or five mines trying to suck off the same patch, and ending up just draining power. Other buildings wouldn't be built through that map, but the two would show up on the other with areas marked unbuildable, such as an area on the metal map where a plant existed, would be unbuildable, and on the normal map, an extractor would be considered an unbuildable obstacle.
Posted: 25 Jul 2005, 09:21
by AF
No the other way round, metal extractors are likely to have already been built in the area by the time its reached by the main base.
Yuk circle maths, hhmmmm, I will generate such an overlay for every type of mex that's found in the AI Def since 2 extractors of different type can mine the same area together. I'll label all sectors that're within mining radius as bad, and the surrounding few as not v.good so that emxes arent buil on the edge of another mexes radius. But I dont like circle maths,
Posted: 25 Jul 2005, 10:08
by AF
http://www.the-wabe.com/notebook/em-algorithm.html
EM algorithm
Motivation:
A method for finding maximum likelihood estimates,
-either in presence of missing data.
-or when the model can be simplified by adding `latent parameters'.
Posted: 25 Jul 2005, 13:00
by AF
Code: Select all
void Util::sortmetal()
{
float3 temp;
float3 highest;
float3 lowest;
lowest.z = 2000;
highest.z = 0;
mp=0;
for(int eek=0; eek<=(x/8);eek++) //X
{
temp.x=(float)eek;
for(int yuk=0; yuk<=(y/8); yuk++)//Y
{
temp.y = (float)yuk;
temp.z = (float)Getmetalval(temp);
metalarray[eek][yuk]=temp;
if(temp.z>highest.z)
{
highest = temp;
}
if(temp.z<lowest.z)
{
lowest = temp;
}
mexpositions[mp]=temp;
mp++;
}
}
quicksortZ(mexpositions,mp,0);
}
int Util::Getmetalval(float3 pos)
{
int val;
const unsigned char* toot = GCallback->GetMetalMap();
val = toot[(int(pos.y/8))*GCallback->GetMapWidth()+(int(pos.x/8))];
return val;
}
//Quick Sort Functions for Descending Order
// (2 Functions)
void Util::quicksortZ(float3* array, int top, int bottom)
{
// uses recursion-the process of calling itself
int middle;
if(top>bottom)
{
middle = partition(array, top, bottom);
quicksortZ(array, top, middle); // sort top partition
quicksortZ(array, middle+1, bottom); // sort bottom partition
}
return;
}
//Function to determine the partitions
// partitions the array and returns the middle index (subscript)
int Util::partition(float3* array, int top, int bottom)
{
float x = array[top].z;
int i = top - 1;
int j = bottom + 1;
float3 temp;
do
{
do
{
j--;
}while (x >array[j].z);
do
{
i++;
} while (x <array[i].z);
if (i < j)
{
temp = array[i]; // switch elements at positions i and j
array[i] = array[j];
array[j] = temp;
}
}while (i < j);
return j; // returns middle index
}
Would thus dump all mex positions usable or not into an array of float3's and then sorts them so that those with the highest metal values are at the top and thus can be sequentially checked to see if there's a mex ontop of them and then given as build co-ordinates. Improvements would be to reduce the size of this array so that lets say anything under the average metal value isnt stored. Or perhaps a better sorting algorithm. Also it doesnt account for the fact there are different types of mex and their extractor radius. A function should be written to remove sectors that're adjacent to eachother or overlap with other mex extractor ranges.
I post this here for suggestions & improvements, and because zaphod says his extractor algorithm is crappy so he's waiting to steal mine.
Posted: 28 Jul 2005, 17:08
by AF
I can compile my AI and load it.
In the following, if I take out the creatgroup functions it'll run through the for loop then crash to desktop. It never gets to the point of calling quicksortZ, and the furthest alogn I can get a response is the "another iteration" create group marker. I dont know why spring crashes tot he desktop at all. Any help?
Code: Select all
for(int eek=0; eek<=(x/8);eek++) //X
{
temp.x=(float)eek*8;
for(int yuk=0; yuk<=(y/8); yuk++)//Z
{
temp.y = (float)yuk*8;
temp.z = (float)Getmetalval(temp);
metalarray[eek][yuk]=temp;
if(temp.y>highest.y)
{
highest = temp;
}
if(temp.y<lowest.y)
{
lowest = temp;
}
mexpositions[mp]=temp;
mp++;
}
GCallback->CreateGroup("another iteration");
}
GCallback->CreateGroup("array filled");
quicksortZ(mexpositions,mp,0);
Posted: 28 Jul 2005, 17:53
by AF
Engine crashes on callback->GetMapName execution
Posted: 28 Jul 2005, 19:21
by b1ind
Just a quick note, since this is a sorting function and might be important in terms of speed, i suggest doing the x/8 once, instead of on each iteration.
Why not just:
Code: Select all
for (temp.x = 0; temp.x <= x; temp.x += 8)
Anyway, nitpicking.. no idea what the crash is... You sure you want <= (x/8) and not < (x/8)?
Reading your last post now.. is there still a problem with the sortmetal function? Or was it just crashing earlier?
PS: You have an uncanny ability to use strange var names.. lol
*edit*
Hey, I'm wondering if you could just use std::sort w/ a callback comparison function. Might save you some headache.
Posted: 28 Jul 2005, 19:46
by AF
I wouldnt know howto use std::sort.
I was annoyed by mex placement for a long tiem so havign finally got it I used iffy names to express my anger beforehand. I thought I had it all doen but when testing ti just crashes the game, I've commented out the code in question and can now start the game off, though I ahve more bughunting todo, primarily with loading an OTA AI definitions files.
And I'll try changing the for loop as you suggested. I cant test it out right now tho.
Posted: 29 Jul 2005, 00:06
by b1ind
Hey alantai, I was thinking of your metal problem and the circle math stuff you were talking about and a few things came to mind. Firstly, for simplicities sake, you could always have the ai ignore enemy metal consumption. Making that assumption, you could store a vector (array) of existing AI extractors. To figure out if a spot is at maximum efficiency you only need to verify that it is at least a minimum of 2*extractor_radius away from all other metal extractors. That would be a quick query since you could just compare the squares. Anyway, some food for thought to hopefully speed up your ai progress.
About std::sort, it works like this.
Code: Select all
// v is a stl container (vector for example)
std::vector<TYPE> v;
struct ComparisonFunction
{
bool operator()(TYPE *a, TYPE *b)
{
// Compare a and b, return whether a should be closer to the beginning (descending order)
}
}
std::sort(v.begin(), v.end(), ComparisonFunction());
// v is now sorted in descending order
See
}
http://www.codeproject.com/vcpp/stl/stdsort.asp for more information.
Posted: 29 Jul 2005, 00:44
by AF
hmmm the metal extractor algorithm is one I dont like to think off, it gets me confused and I tend to greatly overcomplicate the process and burn out.
Posted: 29 Jul 2005, 21:09
by AF
I think that the AI onyl has a limited amoutn fo tiem to do everything, otherwise it doesnt keep up with the engine and the engine crashes. Hence why at the moment the two biggest obstacles are being caused by iterative loops.
The mex algorithm, and the OTA AI definition parser. The OTA def parser loops parsing the file word by word untill it just snaps and crashes for no reason. The unit name it tries to parse at that point is the arm maverick.
Commenting out the parsing code creates a second error when trying to find the best metal extractor todo the job. Which would then crash anyways because the mex algorithm didnt find available mex positions so ther'ell be a crash tryignt oreference a value that ahsnt been put in yet.
I'm guessing that the AI definiion file could be made smaller, and the mex algorithm should be changed so that it at least only does the sectors near to the commander startposition and not iteratively go through every single subsector on the map, making large maps an AI no-go zone. I dont knwo how I'd do that though, I tend to voercomplicate these sorts of things visually and get nowhere when there's a simple solution...
Posted: 29 Jul 2005, 21:48
by b1ind
You should probably think about doing somthing similar to the 'slow update' for pathfinding. It would be silly if you re-attempted to find the best mex spot every ai tick. You should try and allow the trickier (slower) code to execute over a number of ai ticks. After all, if an AI is to seem human, it would be unrealistic that it could find the absolutely optimal mex position in .01 of a second. I also know that this will probably be pretty tricky to do, so good luck!
When much gets back you guys should try collaborating more. Everyone wants an ai. After one is out, then you could make a separate challange to attempt to build the best ai. :D
Posted: 29 Jul 2005, 22:02
by AF
It doesnt call the function every tick,.
The AI calls SortMetal() which has the iteration you saw above. It shoves all the available mex positions into the mexpositions array, which si then sorted using quicksortZ().
When we want to build a mex we simply call GetMetalPos. GetMetalPos looks at Mexpositions[mxp] where mp is the number of positions found, then it decrements mp and returns the position held in the array.
SortMetal is called in the AI initialisation, PutInHat which deals with parsing AI definitions is called in the first frame. It doesnt matter what frame PutInHat is called be it after 30 secs as originally or first frame, it always crashes the engine.
Also, Munch offered to help with a mex extraction algorithm, which he did to an extent before family and holiday tookhim off somewhere.
Posted: 29 Jul 2005, 23:07
by Triaxx2
Does it sort by closest position? Or largest deposit? I always go for what's bigger, but most would go for what's closer.
Posted: 30 Jul 2005, 01:24
by AF
I checks the metal value of each subsector one by one, adding the 2D position and metalvalue to the array, then it sorts them so the values get higher as you move along the array. Then the mex positions are chosen by crossing off the positions starting with the last in the array.
Posted: 30 Jul 2005, 02:20
by AF
Code: Select all
void Util::sortmetal()
{
float3 temp;
float3 highest;
float3 lowest;
lowest.y = 2000;
highest.y = 0;
mp=0;
metalarray = new float3*;
mexpositions = new float3;
int x8 = x/8;
int y8 = y/8;
for(int eek=x8; (eek<=x8) && (eek>(x8/2));eek--) //X
{
temp.x=(float)eek*8;
for(int yuk=y8; (yuk<=y8) && (yuk>(y8/2)); yuk--)//Z
{
temp.y = (float)yuk*8;
temp.z = (float)Getmetalval(temp);
metalarray[eek][yuk]=temp;
if(temp.y>highest.y)
{
highest = temp;
}
if(temp.y<lowest.y)
{
lowest = temp;
}
mexpositions[mp]=temp;
mp++;
}
//GCallback->CreateGroup("another iteration");
}
quicksortZ(mexpositions,mp,0);
}
Thats the entire function, with a few minor changes. The reason for temp.y = (float)yuk*8; is because the metal map returned by the callback interface is 1 eighth the resolution of the full map.
Posted: 30 Jul 2005, 02:24
by Triaxx2
Ah... Not quite what I was talking about, but alright. I meant, does it choose for each con unit based on the distance to that target? Or the amount of metal that would be gained?