Jump to content
  • Advertisement

Archived

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

Isokron

RTS AI

This topic is 5266 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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!