Optimal Metal Extractions
Moderators: hoijui, Moderators
Optimal Metal Extractions
*deleted*
Last edited by Kelson on 27 Jan 2006, 21:25, edited 2 times in total.
Havign skimmed over the last two posts, I have a set fo thoughts that goes beyond the limited confines you have set yourself because this suggestion takes into account terrain, accesibility, and enemy threats, aswell as possibly makign the mex algorithm for segregated and spaced over time.
Starting with gabbas initial research into pathfinding and the details shown by voronoi diagrams.
s can be seen in the diagram below, the blue lines are the lines generated. A voronoi diagram is one where each lines is equidistant between its 2 closest neighbours, and is the furthest from any point it can be without being closer to another point.
Here I've taken the yellow to be metal distribution in this hypothetical map. I have then drawn bounding boxes around the map specifying where the metal is. It is not accurate, it is only as accurate as saying, in this area there is metal. From this a line is drawn to the nearest line on the voronoi diagram, preferably at a 90* angle.
The voronoi diagram in memory is kept as a set of vertexes and lines, each with an associated set fo values, be it for trafficability, threat etc. This can be used to assess a metal regions value straight off. The lines branching off the diagram to the metal zones will have their own data structure as the rest fot he diagram, but this will be dependant on the line in the digram ti is connected to. That copy will then be transformed based on the size fo the area it connects, the total metal value, and the nubmer of mex positions within that area that have been found.
This way we need not evaluate metal data till we need it, and we need not evaluate the map as closely first time round as we do when finding the optimum positions of mexes, at which point we parse through a region as and when we need it.
Which region is better is chosen using the stats on the diagram, using this method the AI will not evaluate any mex positions near to the enemy commanders region untill they appear to be more suitable than any of the remaining positions in the AI's territory. It also means that different gameplay will result in different choices as the time goes on.
By using this method, the longevity of a mex can be better leveraged, and thus its profitability cna be increased. Whatsmore paths for con builders can be generated by ordering the chosen mexes in order of when they intercept the diagrams lines relative to where the builder currently is.
This also implements a basic framework from which other AI systems can be created that are far better than the existing methods. For example, there are cases where this sort of representation of data is better than a matrix style representation, and sometimes a combination of the two makes for better information.
Also the data also suggests wether ti si safe to put more resources into region a to get mohos than region b or to just build mexes. Using this method you can determine the safest existing places and plan to suit as the data changes.
Starting with gabbas initial research into pathfinding and the details shown by voronoi diagrams.
s can be seen in the diagram below, the blue lines are the lines generated. A voronoi diagram is one where each lines is equidistant between its 2 closest neighbours, and is the furthest from any point it can be without being closer to another point.
Here I've taken the yellow to be metal distribution in this hypothetical map. I have then drawn bounding boxes around the map specifying where the metal is. It is not accurate, it is only as accurate as saying, in this area there is metal. From this a line is drawn to the nearest line on the voronoi diagram, preferably at a 90* angle.
The voronoi diagram in memory is kept as a set of vertexes and lines, each with an associated set fo values, be it for trafficability, threat etc. This can be used to assess a metal regions value straight off. The lines branching off the diagram to the metal zones will have their own data structure as the rest fot he diagram, but this will be dependant on the line in the digram ti is connected to. That copy will then be transformed based on the size fo the area it connects, the total metal value, and the nubmer of mex positions within that area that have been found.
This way we need not evaluate metal data till we need it, and we need not evaluate the map as closely first time round as we do when finding the optimum positions of mexes, at which point we parse through a region as and when we need it.
Which region is better is chosen using the stats on the diagram, using this method the AI will not evaluate any mex positions near to the enemy commanders region untill they appear to be more suitable than any of the remaining positions in the AI's territory. It also means that different gameplay will result in different choices as the time goes on.
By using this method, the longevity of a mex can be better leveraged, and thus its profitability cna be increased. Whatsmore paths for con builders can be generated by ordering the chosen mexes in order of when they intercept the diagrams lines relative to where the builder currently is.
This also implements a basic framework from which other AI systems can be created that are far better than the existing methods. For example, there are cases where this sort of representation of data is better than a matrix style representation, and sometimes a combination of the two makes for better information.
Also the data also suggests wether ti si safe to put more resources into region a to get mohos than region b or to just build mexes. Using this method you can determine the safest existing places and plan to suit as the data changes.
Terrain obstacles are generated using a mixture of height and slope, it uses a very similair approach to pathfinding, and in the end it should have information on the terrain about it's accesibility, which is used to generate the diagrams. However if this was patfinding, that diagram wouldnt get generated, and paths would be generated on that data based on what parameters there are from the units, which is what you're talking about.
Hello there AF, I'm happy that my research was of some use to you! Not everybody has the time and patience of digging into this kind of stuff. It has never been used in AI/Pathfinding as far as I know, and Spring is an ideal testing ground for this, because we don't have stupid deadlines to meet.
You guys not gonna see me much on the forum these times around, 'cause I'm starting software engineering studies. Too many math classes for my taste, I'm getting headaches. But I'll keep lurking!
As for defining what is a terrain obstacle, you could base yourself on what terrain is accessible by all land units, and mark off special areas that are only accessible by some units. The AI would use a voronoi diagram based terrain accessible to all; then it's less likely that it sends a task force that ends up going too slow over rough terrain, or getting stuck. But it could take into account the special regions when it wants to make surprise attacks and stuff.
You guys not gonna see me much on the forum these times around, 'cause I'm starting software engineering studies. Too many math classes for my taste, I'm getting headaches. But I'll keep lurking!
Actually on a Spring map there's no "empty space", because you count in the map boundaries to make the voronoi diagram. On a totally flat map, the voronoi diagram would not be undefined: it would be a single dot at the center of the square.cain wrote:the problem on this approach is that the definition of "terrain obstacles" varies from unit to unit, and a vornoy diagram for an empty space is undefined (or unlimited)
As for defining what is a terrain obstacle, you could base yourself on what terrain is accessible by all land units, and mark off special areas that are only accessible by some units. The AI would use a voronoi diagram based terrain accessible to all; then it's less likely that it sends a task force that ends up going too slow over rough terrain, or getting stuck. But it could take into account the special regions when it wants to make surprise attacks and stuff.
Gabba and Cain, while I think the topic is interesting (and it forced me to look up the voronoi diagrams), if you could post a new topic to deal with that subject it would be appreciated (that way, this topic can either die...or material relevant to finding optimal constant-sized circle coverings for abitrary shapes can be posted).
I was just going to send a pm so we could resolve this, but I'm sure more people will respond to this and further devolve it. I would still like an admin (AI has no mods) to lock the thread.
Information not directly pertaining to covering an arbitrarily shaped metal distribution (determined by finding all spots with greater metal value than the minimum allowed due to efficiency trade-offs - this may create islands in the data that would have arbitrary shapes) would be considered off topic. I find the discussion regarding pathfinding interesting, but I would really like some help on the concrete problem stated in the opening post.
What was provided was not a new way of looking at the information provided or adding it to something else, it was a different discussion and a derail. You might find this reply somewhat harsh, but this is my second derailed thread and so far I've found nothing returned for my postings besides flames and off-topic issues that, while interesting, don't assist the threads. Or perhaps, Triaxx2, since you seem to know no one is derailing the thread, you could private message me to show the relationship between the replies and optimal coverings of arbitrary shapes using constant-sized circles (where optimal means a minimum circles, minimum overlap, yet complete coverage).
Admin, please lock the thread.
OT) Thank you Gabba, I have been checking out the information. I also appreciate your deleting the post.
The topic of this thread is optimal mex placement. Not solving the travelling salesman problem (how do I get to each optimal location most efficiently), not avoiding threats, not dealing with terrain obstacles, and not worrying about anything except outside of finding optimal locations for the metal map that manage to cover the maximum (with respect to metal income vs investment efficiency) metal with a minimum of metal extractors. As I replied to AF in the 5th post of the thread - those issues are all a step above the current problem. They all assume we have the optimal locations and are now looking at how to have the AI decide which ones to use, how to get to them, and (from a nice counter-view) how to quickly destroy enemy metal extractors.Triaxx2 wrote:Kelson, no one is 'derailing' the thread. It's simply a new way of looking at the information you provided, and adding it to something else.
Information not directly pertaining to covering an arbitrarily shaped metal distribution (determined by finding all spots with greater metal value than the minimum allowed due to efficiency trade-offs - this may create islands in the data that would have arbitrary shapes) would be considered off topic. I find the discussion regarding pathfinding interesting, but I would really like some help on the concrete problem stated in the opening post.
What was provided was not a new way of looking at the information provided or adding it to something else, it was a different discussion and a derail. You might find this reply somewhat harsh, but this is my second derailed thread and so far I've found nothing returned for my postings besides flames and off-topic issues that, while interesting, don't assist the threads. Or perhaps, Triaxx2, since you seem to know no one is derailing the thread, you could private message me to show the relationship between the replies and optimal coverings of arbitrary shapes using constant-sized circles (where optimal means a minimum circles, minimum overlap, yet complete coverage).
Admin, please lock the thread.
OT) Thank you Gabba, I have been checking out the information. I also appreciate your deleting the post.
Kelson, we didnt derail we expanded in a slightly different direction. We're accustomed to what started as one thing turning into another then leading full circle back to the beginning.
That and us AI devs would find a solution that solved many things would be better than a singular solution.
If you argue that people are derailing your thread, your giving your thread a deathcsentence aswell as any ideas that where proposed with it that you think derailed it.
I'm sure that if this thread dies in the next week people will forget about the diagram I posted and they'll forget about what you said unless we respost them in new threads, and people will get tired if ti keeps getting reposted.
That and us AI devs would find a solution that solved many things would be better than a singular solution.
If you argue that people are derailing your thread, your giving your thread a deathcsentence aswell as any ideas that where proposed with it that you think derailed it.
I'm sure that if this thread dies in the next week people will forget about the diagram I posted and they'll forget about what you said unless we respost them in new threads, and people will get tired if ti keeps getting reposted.
Slightly different might be discussing better algorithms for finding the 'efficient' islands of data. Slightly different might be discussing an economic model to assist in determining what is, or is not, efficient. Slightly different might be discussing the efficiency of a greedy algorithm vs optimal algorithm for this problem - ie, is this even a necessary algorithm? Slightly different might be finding optimal locations, while including terrain obstacles.AF wrote:Kelson, we didnt derail we expanded in a slightly different direction. We're accustomed to what started as one thing turning into another then leading full circle back to the beginning.
Off topic is 'what units can efficiently extract metal'. Off topic is 'how do we find construction units to make extractors'. Off topic is 'how do we determine how to path to each optimal location'. Off topic is 'which mods would need this'. Off topic is 'how do we deal with threats'.
Clearly I'm a different type of developer than you.AF wrote:That and us AI devs would find a solution that solved many things would be better than a singular solution.
I have no intention of again making any requests for help in this forum.AF wrote:I'm sure that if this thread dies in the next week people will forget about the diagram I posted and they'll forget about what you said unless we respost them in new threads, and people will get tired if ti keeps getting reposted.
Which is fine. Yet, that has nothing to do with this thread. This thread is focused on analysing data (which can later be used to make decisions based off of). My comments, and you're free to disagree, were to the effect: Don't post in my thread, if you're not posting about the topic.AF wrote:We're more interested in icnreasing the offensiveness of our AI's at the moment than focusing on building power.
How would you like it if you made a thread regarding improved scouting and someone started discussing how to make a parser to categorize units - not to categorize scouts specifically, not specifically related to scouting - a completely seperate topic? That's all I'm saying.
Bear with me a moment on this. The original post, was that none of the AI's use optimal mex placement, because they average the metal in an area, and drop a mex in one spot, recieving less metal, because they miss the metal on the ends. Correct?
AF and the others, were discussing construction unit pathing.
The actual relationship between the two is rather simplistic. An AI detecting a metal vein of 6x3 will average out a metal extractor dead center. However, if it's including optimum pathing, and distance from cons in it's calculations, it's going to see that it can recieve the same metal by placing a mex with two different cons, each roughly the same distance away, on opposing sides.
Thus the metal is harvested on both ends of the vein. But if it's just dropping from the closest con, without taking distance and realitive speed into account, it'll think it'll get more metal faster by just laying down one in the center.
AF and the others, were discussing construction unit pathing.
The actual relationship between the two is rather simplistic. An AI detecting a metal vein of 6x3 will average out a metal extractor dead center. However, if it's including optimum pathing, and distance from cons in it's calculations, it's going to see that it can recieve the same metal by placing a mex with two different cons, each roughly the same distance away, on opposing sides.
Thus the metal is harvested on both ends of the vein. But if it's just dropping from the closest con, without taking distance and realitive speed into account, it'll think it'll get more metal faster by just laying down one in the center.