• Advertisement

Archived

This topic is now archived and is closed to further replies.

RTS AI

This topic is 5024 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been working on a ~19th century RTS game for some time where the game mechanics, networking, graphics etc have now reached a ... functional stage. So now I want to start implementing a single player AI into it. First some of the major things that differs in it compared to other RTS games. The main objectives in the game is to take your opponents cities since those are where you get your income from. You cant build new or raze cities (although they can be temporary disabled by heavy fire). So the only building stuff you need to think about is factories to produce new units and defensive buildings. Two interrelated concepts that is not normally found in RTS games is land ownership and supply. Every square of the map is owned by a player. The way to take control of a square is to move a unit sufficently close to it. Also squares will slowly revert ownership back to the player controlling the closest city. The units in the game need supply to fight efficently and cities need supply to generate incomes. Supply flows from your capital to other cities where its stored and then flows on to your units. On the way from the capital->city supply can flow without resistance along roads and with progressivly more resistance on fields/forests/mountains etc. From city->units the supply also meets some resistance at roads so you ideally want to fight as close to one of your cities as possible. The link to land ownership is that supply can only flow on your own land so if you can surround an enemy army it will not receive any supply and collapse in some time. I guess thats the major things that a strategic AI need to know about right now. At the moment im planning to have a three level AI approach. The first level is the unit AI that do pathfinding for units, fire at enemies in range etc. This is more or less finished. The second level is what I call the army level AI. This level is supposed to be used definable via DLL files. It replaces the standard hotkey groups found in other RTSes. So when you create a hotkey group you can also select what AI (in a DLL) will control it and the AI then control the units in the group and decides what commands the user can give it. I have some sample DLLs finished for this level but is planning to create some more. The third level is what I call the global AI. Its supposed to be able to play the game on its own with no outside input. This is what im currently thinking about how to implement. My current plan is something like dividing it into one defensive and one offensive part. The defensive part will study the land ownership map to see if any enemy armies seems to be incomming. Then send out some scouts to assertain their size and deploy a suitable counter army to the closest friendly city. The offensive part should build up some strength and then choose a enemy city to attack (using a graph of how cities are connected) and then try to attack it. Tactical finesses are supposed to be handled by the army level AI although its currently not up to it. So any input about the above is welcome but I would especially like to hear about the following. How to improve the global AI. For example using some sort of gas flow simulation like in http://www.movesinstitute.org/Theses/BurgessThesis.pdf to find bottlenecks seems cool, but im not sure what to use the results for. Keeping an army ordered when its stationary is easy but what to do when its on the move? Most games seems to keep the armies formed in aproximatly the same way when on the move but that doesnt work here since different terrain types have very different movement costs, a road through a forest is >10 times faster to move on than the surrounding forest. Currently I let each unit pathfind its own way to the goal which work ok except that the army turns into a mob as soon as it starts moving. So how to keep an army in some order while still allowing it do deform into a single or close to single column? On a related note how should the strategic AI select routes so it doesnt get stuck fighting in a forest or someting which will probably slow it down a lot? The current version of the game can be downloaded from www-und.ida.liu.se/~stejo127/bagge.rar Also here is two screenshots www-und.ida.liu.se/~stejo127/rts1.jpg www-und.ida.liu.se/~stejo127/rts2.jpg

Share this post


Link to post
Share on other sites
Advertisement
Isokron,

I like your idea for a 3 level AI - seems perfectly natural. I also like how you plan to divide the global AI into defensive and offensive. Since supply is a big part of your game, I''d charge the defensive part with defending supply lines and use the offensive part to disrupt your opponent''s supply lines. A secondary goal of the offensive part would be to expand territory.

I''m not sure what you mean by bottlenecks, but if you mean terrain features that force units into a smaller area then you can use some even simpler algorithms to find them - think flood fill.

Moving units in formation is one of the hardest things to do in an RTS. Very few companies do it well (or even attempt it). You want to avoid pathfinding every unit in the formation - pick one and pathfind him. Then make sure all the others stay with him as he moves (not at all trivial, but I can''t give everything away). One of the hardest parts is modifying your pathfinding system to handle very large units. Or should I say it''s hard to do without enduring severe CPU hits...

All in all, I think you''re off to a very good start - most budding AI developers don''t get to the point you''re at already!

Bob Scott
AI Designer/Programmer
Stainless Steel Studios

Share this post


Link to post
Share on other sites
Taking supply lines into account would probably be a good idea. To defend them I guess one can just find the best one by doing a pathfind from source to destination and try to keep it open. In a way my army AI already do this by keeping units patroling back and forth to the closest city. To attack them succesfully you would have to find all alternative routes also which would require an iterative pathfinding where you add a penality to already used paths. This feels rather expansive cpu wise or is there a better way ?

With bottlenecks I do indeed mean terrain features that will force the opponent into a limited space although I dont think a floodfill could work for me since my terrain has no real blocking areas just lower or higher movement cost (you can move through a forest its just slow and you will have problem with supply)

I have thought a bit about having the army follow a single leader doing the pathing but to me it seems to have to many problems to be worth it. To begin with for small movements you dont want the army to que up and stuff but rather just move straight ahead. Also if your army stand in front of a small forest or lake and are ordered to move to the other side you might want it to split so half move to the left and half to the right of the obstacle. This sort of things seems quite hard to detect while if you do an individual path search for the units you get them for free.

I dont really have a problem with cpu usage during pathfinding since my pathfinder can initialize just about any path on my 512*512 map in about 0.1ms. Also I think its architecture should lend itself quite well to detect partially identical paths and reuse parts of them if I want to trade complexity for speed in the future.

Instead what I dislike about the current solution is the way it makes the army look like a mob and also that the infantry has a tendency to outdistance the artillery and leave it vulnurable. I guess a simple solution would be to slow down units to match speed with the slowest but that would probably lead to trafic jams and increase the overall travel time for the army.

Share this post


Link to post
Share on other sites
quote:
Original post by Isokron
Instead what I dislike about the current solution is the way it makes the army look like a mob and also that the infantry has a tendency to outdistance the artillery and leave it vulnurable. I guess a simple solution would be to slow down units to match speed with the slowest but that would probably lead to trafic jams and increase the overall travel time for the army.


I''m not sure what you mean by "looking like a mob" unless you mean they crowd together. You can use a sort of flocking algorithm that will keep space between units as well as keep them relatively together (which helps in your infantry/artillery problem). You would still pick on leader but instead of having them directly move TOWARD this leader, they would move toward him but follow the rules of flocking as well. While flocking rules will give you a slight time hit, you can peform the actual "leader find" routine less often to make up for it.


Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Flocking behaviour would fall under my definition of looking like a mob. What i mean with mob like behaviour is how all subgroups etc lose cohesion and you just get well a mob. Compare this to how a traditional army moved if they expected to go into battle formation. Usually they had what was intended to be the right flank on the head of a column (or several) that then turned 90 degrees on the battle field and moved up to a line. While I dont want this degree of order something a bit more ordered would be nice.

On the other hand I guess that if historical generals had units that could go from a mob like state to ordered lines the way mine can they wouldnt care so much about march order (well at least after stopped staring in disbelief).

So I guess im just asking for the impossible, somewhat simple code, optimal move time and somewhat ordered behaviour.

Share this post


Link to post
Share on other sites
Do these help...
http://www.gamasutra.com/features/19990122/movement_01.htm
http://www.gamasutra.com/features/19990129/implementing_01.htm
or is the scale wrong?
I love the idea of supply lines affecting a game. I'm looking at something similar using lines of communication with suitable delays.


[edited by - tonyg on May 13, 2004 8:32:04 AM]

Share this post


Link to post
Share on other sites
For defense, I would just have friendly troops patrol back and forth along your patrol lines.

For offense, look for enemy troops that are patrolling (chances are the player will do the same thing).

You can still use floodfill for finding bottlenecks - instead of looking for terrain features, just look for the cost of travel over a tile to be above a certain threshold.

Re: formation moving - matching velocities is not a good solution. You end up with very slow formations if they contain any slow units in them, which will hinder not only attack speed but retreat speed. Unless of course you average the speeds (but then people tend to complain about "speedy trebuchets" and the like). I like the idea of using flocking for formations, but am also worried about the cpu hit with dozens or hundreds of them on the map. BTW - properly created flocking behaviors shouldn''t look like a mob. The rules could be: 1) follow the leader and 2) keep a minimum distance between the other units in the formation.

Bob Scott
AI Designer/Programmer
Stainless Steel Studios

Share this post


Link to post
Share on other sites
Since you don''t need exactness in your flocking as there are no "sudden moves", you can spread the flocking checks out over quite a few time slices. That spreads out your hits and isn''t so CPU intensive. As Bob pointed out, too, you don''t need the full flocking rules. You don''t need to align direction of travel, you are following a leader. You don''t need to match speed, you are following a leader.

One thing I would suggest is the "inviso-leader" concept. put a point out in front of the group that is the leader and have people follow that - with one exception: Don''t get within X range of it. That will keep faster units from jumping right up to the leader. All you would need is a range check. If it''s less than the desired range, match leader''s speed.

The reason I would use the inviso-leader is if it is one of the units, you will get a "boat wake" sort of effect behind him. At least that''s what my Vicodin-drugged brain is imagining right now.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
tonyg: Yes thats the sort of thing im looking for. Only problem is that it sort of assumes that large part of the map will have large areas of terrain with the same movement cost. This is not true for me since I in my map the roads are the fastest alternative in many cases. So to use them the army would have to form up in a single column. This could be easily implemented just letting the units know of the unit before and after. Trying to keep a certain distance to the unit before (but reusing his pathpoints so you dont get a corner cutting problem) and slowing down if the one behind fall to far behind. The problem here is that such a column could stretch out 1/4 of the map for a large army which would increase travel time a lot. So to fix that one could not bother forming a colum for short movements, form multiple columns when applicable, let the fastest units travel beside the road (wont work well with roads through forests). So one get a lot of special cases to take care of that is done more or less automatically with my current individual pathing approach, although in an unordered fashion. But i guess I will have to swallow the bitter pill and do a lot of coding if I want to get ordered armies with good travel times.

eeaiguy: The problem I see with patrolers for defense is that if the opponent place a group of units on your patrol route they might arrive one and one and be defeated before the next arrive. Better would be to detect when an opposing group threaten a supply line and send out a suitable counter force. Although the question is how to detect that in time.

Looking for enemy patrolers seems like a bad idea for two reasons. It would mean you could secure your supply route by not securing it and also you would probably only patrol the best route not alternative ones.

Im unsure how you mean one can use floodfill to find bottlenecks. Even if a threshold that works everywhere is found I cant see how you can use the floodfill to gain more than very local information.

Share this post


Link to post
Share on other sites
You do need to make sure that your patrolling defenders travel in packs and don''t get isolated for this type of defense to work.

As far as detecting enemy supply lines - is there any other unit that travels the route (like carts) or is it an implied route between towns? If the latter, you might have to pathfind between the 2 towns and pick a spot to place your troops.

If you use floodfill to create a container full of points (say with the highest movement cost), you can then do an area analysis on the points to determine where the center of the mass is.



Bob Scott
AI Designer/Programmer
Stainless Steel Studios

Share this post


Link to post
Share on other sites
Yes i guess patrolers in packs could work somewhat well.

Supply lines are entirely implicit since I couldnt find a way to do them optimal otherwise. And if they where not optimal the players would want to micromanage them (death to mm is one of my main design goals).

I still dont get your floodfill algorithm for finding bottlenecks. Here is two screenshots from a typical map from my mapgenerator natural colors and
color coded for height . The darker greens are forests and the blue is water. These toghether with the places with a step slope is expensive. How would you figure out the bottlenecks between blue and red cities using floodfill on such a map ?


[edited by - Isokron on May 15, 2004 5:11:16 AM]

Share this post


Link to post
Share on other sites
Hey Isokron, your game looks really sweet I thought that no one would ever try to make an RTS with original mechanics (different from Blizzard-style games).

Ok, breaking up the AI in 3 levels is a really good idea. But I don''t think you realized how handy this can be for the formations. If you add another level you''ll see it''s much easier: you can have the highest level (kingdom or something); then the armies, made up of groups; groups (formations) like the reserve, the flanks, etc; and finally the individual soldiers. For simplicity, each group only contains soldiers of the same "type", like one or more groups of infantry, groups of cavalry, etc. This helps a lot because if the soldiers use different rules for formations inside a group, you''ll have no cohesion at all. Just like if you had no "group" level between armies and soldiers (that''s why this topic always gives game developers an headache

You can use simple steering behaviours to align the soldiers with each other inside a given group, and to align the groups with each other according to the tactics. Here''s an excellent article on them that describes just about any behaviour that you might need:

http://www.red3d.com/cwr/steer/gdc99/

It''s kinda hard to read in the beggining but when you start seeing how useful it is, you''ll see it''s much easier =)

So, you could use some simple rules to make each soldier face the direction of the leader, try to align himself with a soldier to his right and another to his left, and you have line formations inside a group. You can then define rules like the right flank (a group, not a single soldier) is to the right of the main body, the left flank is to the left, the reserve is behind, the cavalry is somewhere else (hey I''m no expert in battle tactics ), etc. The groups will move to fill those places and the soldiers will move to follow the group. Then you can order an army to move to the battle grounds, detach the main body to charge at the enemy, order the right flank to move forward, the cavalry to flank them, etc. I think it would be a much more fullfilling experience than micro-managing individual soldiers that should know what they''re doing

Share this post


Link to post
Share on other sites
Isokron,

The flood fill is just a first step - you want to use it to create lists of "areas". Things like forests, lakes, impassible mountain ranges, etc... Once you have these areas, you can figure out the distances between them and find out which ones are "close" to each other. That''s a bottleneck.

For grouping coordinates into "areas", you might look into the concept of convex hulls.



Bob Scott
AI Designer/Programmer
Stainless Steel Studios

Share this post


Link to post
Share on other sites
Jotaf: Thanks for the encouragement, I am not that big a fan of most "modern" RTSes still prefering good old Total Annihilation.

I already have a level between the army AI and the unit although its quite a bit different from your idea and is mostly there to save network trafic. I call it a squad and it contains 4 infantry or 3 cavalry or 2 artillery etc units. The player cant give orders to the individual units but only to one squad at a time.

As for larger groups inside an army I want to give the one that creates an army AI as much freedom as possible so I wont create any hard divisions like that, although I might implement an army AI that uses that sort of decomposition.

eeaiguy: Ah I see now what sort of algorithm you mean. It would probably work although it will not give as much info as the gas flow analyzis i proposed.

Share this post


Link to post
Share on other sites
Isokron, have you looked at the game Kohan? If not, it may be worth checking out. They did some interesting things with ''squads'' and land ownership. Interesting mechanic changes, etc.

Share this post


Link to post
Share on other sites
Well, I didn''t say it needed hard divisions. When organizing an army, you start with X cavalry, Y infantry... and you assign them to different groups and give them names (left flank, artillery, etc). Then you give them generic orders about their initial positions (this could be done by dragging them around a representation of the battlefield). When preparing for battle, they automatically go to those positions. Or you give names to different configurations ("tactics") and you chose one at the beggining of a battle. Some players would appreciate micro-managing squads (go get Ground Control, they use the same system ) but others would prefer giving those orders I was talking about. Did you read that article about steering behaviours? It should give you some pretty neat ideas for complicated formations, but I can give you some of my ideas too if you want.

Share this post


Link to post
Share on other sites

  • Advertisement