AI method Request

Auto-explore, move AI

Goodmorning all,

One thing I am hoping for in is an improvement in the Auto explore AI.

The GC auto explore AI worked as

'find nearest(to original starting point?) unexplored region, set destination, when arrive repeat.' The algorithm doesn't cause the scout to cross the territory very often, so some use of the current location is also taken into account.

It's a perfectly functional auto explore, but i hope that the Elemental one will be better.

When mapping out a region (in a game where you map perfectly first pass) a much more efficient algorithm would determine the farthest out the scout can be, such that it's field of vision ends at the point it wants to see (and therefore it sees that point, and 2 fields of vision beyond that point,rather then one). and take a curved path to get there.

Unit Y in field, X is unexplored o is explored. d is destination. line of sight is one unit (for simplicity), p is path, S is starting point

Y is told to auto Explore,
XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX
XXXXXXXXooYooXXXXXXXXXXXXXXX
XXXXXXXXooooXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX

Turn1
old algorithm                                     Suggested
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX    XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX   XXXXXXXXooopoXXXXXXXXXXXXXXX
XXXXXXXXooYpoXXXXXXXXXXXXXXX       XXXXXXXXooYopXXXXXXXXXXXXXXX
XXXXXXXXoooodXXXXXXXXXXXXXXX     XXXXXXXXooooXdXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX    XXXXXXXXXXXXXXXXXXXXXXXXXXXX

Turn3
old algorithm 5 squares                      Suggested 3 squares
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX     XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX    XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXooSoooXXXXXXXXXXXXXX   XXXXXXXXooSoYoXXXXXXXXXXXXXX
XXXXXXXXooooYoXXXXXXXXXXXXXX       XXXXXXXXoooopoXXXXXXXXXXXXXX
XXXXXXXXXXdpooXXXXXXXXXXXXXX       XXXXXXXXXXdpXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX    XXXXXXXXXXXXXXXXXXXXXXXXXXXX

Turn 4
old algorithm 9 squares                      Suggested 6 squares
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX     XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX    XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXooSoooXXXXXXXXXXXXXX   XXXXXXXXooSoooXXXXXXXXXXXXXX
XXXXXXXXooooooXXXXXXXXXXXXXX    XXXXXXXXooooYoXXXXXXXXXXXXXX
XXXXXXXXXXdYooXXXXXXXXXXXXXX    XXXXXXXXXXdpooXXXXXXXXXXXXXX
XXXXXXXXXXoooXXXXXXXXXXXXXXX   XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX    XXXXXXXXXXXXXXXXXXXXXXXXXXXX

Turn 5
old algorithm 11 squares Suggested 10 squares
XXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXooooXXXXXXXXXXXXXXX     XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX    XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXooSoooXXXXXXXXXXXXXX   XXXXXXXXooSoooXXXXXXXXXXXXXX
XXXXXXXXooooooXXXXXXXXXXXXXX     XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXdpYoooXXXXXXXXXXXXXX    XXXXXXXXXdoYooXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX   XXXXXXXXXXpooXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX    XXXXXXXXXXXXXXXXXXXXXXXXXXXX

Turn 6
old algorithm 13 squares                      Suggested 15 squares
XXXXXXXXXXXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXooooXXXXXXXXXXXXXXX     XXXXXXXXXooooXXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX    XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXooSoooXXXXXXXXXXXXXX    XXXXXXXXooSoooXXXXXXXXXXXXXX
XXXXXXXXooooooXXXXXXXXXXXXXX    XXXXXXXXooooooXXXXXXXXXXXXXX
XXXXXXXXdYooooXXXXXXXXXXXXXX    XXXXXXXXdoooooXXXXXXXXXXXXXX
XXXXXXXXoooooXXXXXXXXXXXXXXX    XXXXXXXXXpYooXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX    XXXXXXXXXoooXXXXXXXXXXXXXXXX

It is trivial to see that the new algorithm will reveal field faster then the older algorithm.

The new algorithm reproduces a maximally expanding spiral search pattern in most instances. It also allows multiple scouts to combine thier efforts with moderately high efficiency without additional code.

Ideally the AI explore algorithm would take into account the number of units and the speed of each unit... but that may be too much to ask, This proposed method would provide a significant boost to explore speed, and automatically provide some ability to efficiently use multiple scouts without explicitly coding rules for those units. Addition bonus for having the path be chosen to maximize the amount of dark area reviled.

Second request, much like the first request.

When a stack of troops march together traditionally the march together at the speed of the slowest member. I would like to request that groups be allowed to made are not required to march together. Clicking on one unit and giving it an order would give all the units the order, Unless the unit in question was broken off from the group (with some obvious UI method of showing they are still grouped.).

This would free up faster scout units to preform scouting and advanced lookout functions for slower tank units.

The UI would have to have an option to force the group to stay together, i would suggest 3 levels of cohesion, One stack, One turn to one stack, and maximal spread.    The middle option would allow units of the group to be no further then a distance which would allow them to group back together in one turn.

The algorithm would calculate when the slowest member of the team will arrive. Then assign each faster method a route that gets them to that destination on the same turn, by way of a less direct curved path(or a path that overshoots the destination, then backtracks to arrive on time, as a look-ahead).

The method would allow Faster units to function as scouts at the risk of being caught/killed or ending up in a different branch and arriving later then expected due to having to correct its course and backtrack. It would add another layer of strategy, do you keep your unites together for safety, or use the fast units as scouts for more information, advanced warning?

As a bonus Troops traveling together could come with the additional bonus of traveling slightly faster perhaps. Fast units carrying the supplies or some of the weight of the slower unites, giving a small boost to the total groups movement speed. Having one fast troop in a large army would provide almost no advantage, but having one slow troop in a large team of fast units would move somewhat faster then the slow troop would move alone. [some form of weighted average, where slower troops have more effect on final speed then fast troops, but a lot of fast troops for each slow troop would result in a speed bonus.]. For example team of pike-men and Calvary. The pike-men don't fight on horse back, but if there are as many Calvary as pike-men the group can travel 2 to a horse. The horses would be slower however for the extra weight (and the clumsy pike), then the Calvary traveling alone.

If that was to be used, the default would be less then a turns ride at all times, spread out would give a scouting bonus, combined would give a small speed bonus.

Just my requests, what does everybody think??

Robbie Price.

Locked Post

Advanced Search

Watch this post

Do not email me updates for this post Email me updates for this post

Successfully updated karma reason!

Your suggested scouting method is interesting - I can definitely see how it would be extremely efficient in certain circumstances, but it doesn't seem particularly adaptive and it also doesn't apply well to rectangular maps...

It's not particularly adaptive (not without major modification, anyway) because if I manually send out a scout in a straight line off in one direction, your algorithm would get all thrown off. And I'm likely to do much more than just send off one scout in a straight line. The auto-explore algorithm needs to be able to take into account all sorts of funny shapes and lines in its 'way.' And on smaller maps, at least, it would get pretty hung up due to the rectangularity of the world...

Successfully updated karma reason!

I don;t see how the search algorithm fails in retagular worlds..

If you are told to auto explore after running a long way you'll end up doing an arc one way, then turning around and doing an arc the other way, (or just jumping accross the gap), it would need to do an edge detect, and not try to walk off the map. . . . but that's one condition.

comparied to the alternitive, 'go to the nearest unseen patch' i fail to see how this method could preform significantly less well.

Note that the auto explore takes the unites starting point as the expand from, not the nearest town, or center town.

can you clarify a situation where the blind go to nearest dark would be better beyond 4 or 5 turns?

Robbie Price.

Successfully updated karma reason!

Quoting Robbie.Price,

reply 2

Well it's more problematic than that. The spiral would essential have to start over every time the unit encounters an obstacle, and as you pointed, your algorithm only really becomes efficient in the long term... If it is constantly starting all over again, it will rarely have an opportunity to enter its efficient stage.

I'm not saying SD should stick with their simplistic and inefficient exploration algorithm, just that I'm not sure how well this would actually work in practice. That said, it could probably be used as a good starting point.

Successfully updated karma reason!

I can't discuss algorithms, but I can discuss from a results-oriented perspective.

What I'd like to see is a scout that spirals out in increasing concentric loops around it's starting point. The 'starting point' being the nearest unexplored or otherwise visible map node.

I need to know the immediate surrounds before I want to see a scout bee-line outward to an extent then run a grid or criss-cross for a bit, then bee-line in on a tangent or right-angle before beginning another criss-cross hatch.

The CompSci majors amongst us would vomit at the inefficiency when looking at time-to-complete a given world map exploration. But this isn't a mathematic puzzle to solve. Reconnaissance has a different set of priorities that aren't usually factored into scout unit automation in the games I've played. I'd like to see exploration AI in Elemental take those priorities into account.

Successfully updated karma reason!

Goodmorning all,

Firstly, I'm not acutally suggesting a fixed spiral solution, the algorithem is simply to aim to go beyond the nearest dark spot, along the line that reveils the most dark spots. The algorithm generates a spiral if started in on one square surrounded by darkness, but that's just one outcome. Also the algorith only fails when the radius of the unknown wall is small, My example was a worse case sanario, and it showed that after as little 5 turns at one step per turn, it is better. Since being dropped in the middle of a black field is uncommon (only for the first 5 turns, or after a random teleport). I can't think of an easier algorithm that is equally sight/turn efficent.

Secondly, Mathmatically the best way to search (the method addopted by flys. insects, and most forging animals) for sparce resourses is to go in one direction randomly, for a random distance, then search around there locally for a random period of time, then run off in a new random direction(again for a random period of time.) This would be a differnt algorithm, but that algorithm in part assumes that the avalibility of resourses in a place will change over time. which is less true of 4x games.

Successfully updated karma reason!

I play Civ4 quite a lot lately, so I'm quite familiar with the challenges of exploration. Due to the lack of decent exploration AI (my scouts tend to scout the coast line, and then die to barbarians), I usualy end micromanaging my scouts.

I think that idealy there would be saveral search algorithems and the player will choose between them for each unit as he sees fit. The algorithms would be devided by their purpose (and not functionality).

Rough exploration - Rough idea of the landscape around you, in a wide area
Methodical exploration - Methodicaly explore the entire region, starting from a set position.
Borders - Send the scout in a single almost linear direction. The purpose being to check the borders of your continent.
Random - why not?

Successfully updated karma reason!

Just thought I'd bump this post as nobody commented on the second half of the OP. I think that having different options for how multiple units stacked together move is a really good idea and would potentially be very easy to implement (at least I think it would, but I'm not a programmer ) while offering a worthwhile increase in strategic options and cutting out some micro (I mean techincally you could do this on a unit by unit basis in most games, but having it done for you on a semi-automated basis would be a lot nicer).

I'm not entirely sold on the bonuses to fast/slow units being stacked with some of the other sort.. I can see how you could justify it from a realism point of view, but I dunno.. I'm not sure what kinda incentive structure it might set up for troop movement in general. It's still intriguing enough to be something I'd like to see beta tested however as it might potentially add some interesting decisions to the game.

Successfully updated karma reason!