Jump to content
  • Advertisement
Sign in to follow this  
MONSTROZZITY

AI for a small RTS

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

Orignally I wanted to try to make an RTS game kind of like supreme commander but I reallized that I have no real idea as to go about the AI creation proccess. Im using Python because Im using Blender 3d which Im very comfortable modeling with and because it has a built in game engine. It seems that most of the posts on this site are about C, C++, and C#. Blender 3d doesn't support them though. Even if you don't know how to go about it in Python then any tips for my consideration would be way more than appreciated. I was planning on making a game simpler than Starcraft 1 but with concepts from supreme commander. I would have a commander unit (I liked that idea from supreme commander), one class of engineer, a hover tank(no need to animate treads if they aren't there!!!) with long range and another with short range, mobile artillery(maybe) A rescource system like supreme commander(mass and energy). Generators, mining station, and factory. No factions.

Share this post


Link to post
Share on other sites
Advertisement
People always talk about building influence maps and doing pathfinding on them; that seems to be a popular approach, but it only really solves a subset of your problems, so I'm also interested to hear answers (e.g., how is resource allocation managed? Timing? etc.)

Share this post


Link to post
Share on other sites
heh. The AI in Supreme Commander isn't actually good at all. (Neither in Supreme Commander 2 if you've played it). Units will sit around and die if they can't attack a target instead of trying to dodge the incoming bullets.

The pathfinding isn't that advanced either. Planes for instance use something resembling boids and so do ground units. There's also an optimized pathfinding system. It's funny though if you play it. Large units literally push other smaller units out of the way as they move. (Maybe just implement a rigid body circle to circle system to perfectly enforce unit boundaries? Boids already has a rule to try to preserve spacing but often units can drift into one another in compact groups).

The main thing you want to look up is concepts relating to boids. With only a few lines of code you can do stuff like naive boids implementation.

Finding how to do pathfinding for groups of units should be interesting. I know there are many queue problems people try to solve. (100 units 3 doors type stuff so that units "flow" evenly through given paths).

Share this post


Link to post
Share on other sites
Start simple. Like stupid-simple. Add complexity later only after you have that working.

So start with forgetting about attempting a skirmish opponent AI. (i.e. the AI that models an opposing player). I've written one, it's super fun but above your head if you're trying to get unit level AI to work. And also pointless working on until you have unit level AI working correctly.

Unit level AI is very straight forward, but there is enough complexity here to keep you busy for a long time.

1) Unit State machine:
Read some tutorials. Foundationally you need onEnter, onUpdate and onExit methods for each state. And you need a state machine to drive the states.

For a basically functional RTS you only need 3 states: Attacking, Idle, Moving
When you get that solid add: Guard (radius tethered, will fight inside that radius), Attack-Move (moving but will break off move to fight and then resume moving)
More advanced will depend on your game but: SpecialPowers, Leaping, Repairing, MoraleBroken, Pinned, etc...

Idle: piece of cake, do nothing. this is your default state
Attacking: relies on other sub-systems - target chooser, weapon system. Most simply: Fire weapon at target.
Moving: relies on other sub-systems - pathfinder. pretty simple, just keep following the current path

2) Target Chooser: this can be either per unit or global. Global is more efficient but probably harder to conceptualize. At it's simplest level this is a simple range check and choose closest enemy; more advanced will tweak the target choosing heuristic to include things like health, effectiveness of weapon, etc. This is not part of the state machine but is a system which the states must be able to query: if (targetChooser->hasTarget()) gotoAttackState()

3) Weapon System: you don't want the AI to drive the weapon system. You want the AI to set a flag on the weapon like bCanFire=true. The weapon runs it's own state machine: reloading, ready, firing. Again not part of the AI state machine but the state machine must be able to control it: mWeapon->startFiring(), mWeapon->stopFiring()

4) Pathfinder: simple A* pathfinding to start. This will quickly become a performance problem so you'll eventually want to move to hierarchical A* (most likely...there are other options but this is relatively standard). Again, outside the state machine but state machine must access it: mPathfinder->getPath(). Instigation of path planning will happen when a unit receives an order; keep the order system abstracted from input so that later on a high level AI can give units orders.

5) Command system. A simple message queue per unit, probably; also maybe not a queue but just an interface for setNetCommand(). You simply add commands to the queue or call the interface, and the state machine controller or states themselves process the commands. Example Commands: MOVE_TO, ATTACK. Each command should have a payload (additional data): ex. in the case of MOVE_TO the payload is a destination, in the case of ATTACK the payload is a target. It's important that you have this so that commands can be abstracted from player input; this will allow you to write higher level AI later

Otherwise I would recommend either a safe-pointer for targets or an id. Units die all the time and you don't want to have to directly manage making sure that no one is holding a bad pointer.

After that stuff get very complicated very quickly. For instance you'll eventually want a group-level AI which will coordinate unit positioning so you get nice spreading out of units like you see in the new SC2 videos. It can also coordinate units for focus-firing and generally help to micro-mananage units if you want to move in that direction. There are tons of other things like allowing certain units to path over certain terrain that other units cannot. Differences between large and small unit pathfinding can also add fun.

This should keep you busy for a year or so. Come back when you want to start tackling player-level AI [smile]

-me

[Edited by - Palidine on February 25, 2010 5:40:44 PM]

Share this post


Link to post
Share on other sites
This is more than I could have hoped for, I appreciate it alot. I won't have alot of free time to work on the project except on weekends, and even that time is limited(I live on a military base for college and my only escape is off base liberty), but Im itching to get to work.

Im getting the feeling that this may be too big a project for me to handle, but heck, I learned how to use blender 3d with youtube alone so I might as well bash through this too and learn along the way.

Im basically getting all of this done in python so I was also wondering if anyone new of any good books that dealt with programming of this nature. And of course youtube will no doubt be a valuable life line. When I get updates (you said this would take like a year so they will be few in between) I will post them up.

Any clue about resource management though?

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
2) Target Chooser: this can be either per unit or global. Global is more efficient but probably harder to conceptualize. At it's simplest level this is a simple range check and choose closest enemy; more advanced will tweak the target choosing heuristic to include things like health, effectiveness of weapon, etc. This is not part of the state machine but is a system which the states must be able to query: if (targetChooser->hasTarget()) gotoAttackState()


Although I don't want to detract from Paladine's very important message of "start simple," and I also haven't implemented a target chooser myself, reading this does make me think immediately of an optimal assignment algorithm called the Hungarian algorithm. At first glance, it doesn't quite solve the problem at hand, but I think that on closer inspection it does, so long as for the purposes of the algorithm you (1) create multiple copies of tasks (so that multiple units can contribute to the same task (e.g., killing a particular unit)), and (2) add "null units" so that the number of workers equals the number of tasks.

That said, this kind of optimality may be more than is necessary. And by "may be," I think I mean, "almost certainly is, if you're honest." But it's still at least academically interesting, and perhaps something to consider eventually as "icing on the cake" for said subsystem.

Quote:

4) Pathfinder: simple A* pathfinding to start. This will quickly become a performance problem so you'll eventually want to move to hierarchical A* (most likely...there are other options but this is relatively standard). Again, outside the state machine but state machine must access it: mPathfinder->getPath(). Instigation of path planning will happen when a unit receives an order; keep the order system abstracted from input so that later on a high level AI can give units orders.


On this subject, an alternative to grid-based hierarchical A* which is becoming increasingly appealing to me is Voronoi roadmap-based approaches. What's nice about the Voronoi graph is that it (1) is small (and so, quickly searched), and (2) feels like a much more natural representation for the connectivity of your level. And although it's often presented as applying to polygonal worlds, there are in fact some very simple algorithms for computing Voronoi diagrams on grids.

Quote:
Original post by xx:
The main thing you want to look up is concepts relating to boids. With only a few lines of code you can do stuff like naive boids implementation.


Boids are great, but if you want reliable behavior with guarantees you may want to use an inter-agent-potential-based approach rather than Reynold's original, which is more ad-hoc. It's still more-or-less the same idea, but a little more principled: You define a potential function over the inter-agent "distances" (which may actually include things like orientation), differentiate it, and then have the agents do whatever moves down the gradient.

[Edited by - Emergent on February 26, 2010 1:37:25 AM]

Share this post


Link to post
Share on other sites
If he has no idea how to write AI, boids, the Hungarian algorithm, influence maps, etc. are SERIOUS overkill. As Paladine stated, just getting a single unit to move in the right direction and engage a target is a lot of work. Start there.

And yes, you are going to run into C[..] because it is what 90% of games are written in. And probably 99% of RTS games. You are really going to have a hard time writing a full RTS AI with Python. Remember, many scripting languages are merely a high level veneer that is laid over the C++ guts of an engine.

I would seriously recommend writing a tank battle game of some sort first. Write something where 2 enemies find, follow, attack, and kill each other. That will keep you busy for a while. After that, it's all variations on a theme.

Share this post


Link to post
Share on other sites
Quote:
Original post by MONSTROZZITY
Orignally I wanted to try to make an RTS game kind of like supreme commander but I reallized that I have no real idea as to go about the AI creation proccess.

Im using Python because Im using Blender 3d which Im very comfortable modeling with and because it has a built in game engine. It seems that most of the posts on this site are about C, C++, and C#. Blender 3d doesn't support them though. Even if you don't know how to go about it in Python then any tips for my consideration would be way more than appreciated.


I imagine that you would get more help with algorithms, here, than with Python specifically. Even a quick search on Bing reveals several resources for game programming in Python, such as:

Python Game Programming Challenge
"Game Programming With Python"
Pygame


-Will Dwinnell
Data Mining in MATLAB

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
If he has no idea how to write AI, boids, the Hungarian algorithm, influence maps, etc. are SERIOUS overkill. As Paladine stated, just getting a single unit to move in the right direction and engage a target is a lot of work. Start there.


Yea I think starting with movement and attack commands would be a good place to start for me, then I could probably incorporate the parts of coding dealing with attack into a turret type programming, then eventualy I could go on to group attack AI, like how to tell them to focus on a single enemy at a time as a group or to break up into individual skirmishes. I'll also look into Algorithms.

I appreciate all the tips from everyone, now I have a good idea were to start and what to look for/expect.

Share this post


Link to post
Share on other sites
Actually Predictor, could you be a little more specific as to how Algorithms could help, or just refer me to another post on Algoritms that might explain a little more in-depth?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!