[General Algorithme] Working with AI

Got questions? Got answers? Go here for both.

Moderator: MaxCoderz Staff

User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

[General Algorithme] Working with AI

Post by kv83 »

Hi!

As you may know most programmers are facinated by AI part of programming a game. But how to make a good AI? I created this tread to discuss different AI's you made, are going to make or thought about.

A nice example for good use for AI are the monsters in ARPG's! I was thinking of a good AI for a guard some days ago.

A guard should move always in the same pattern. From point A to point B. So that part is really simple. But a guard will do other things if the 'enviroment' changes. And here comes the fun part! Wouldn't it be fun if the guard would actually see you? This can be achieved to 'give' the guard a range of sight. When the values player_x and player_y are in the range of sight, it will loose alarm or do another action. Same goes for hearing. If the players moves a block, or kills a enemy with his sword, it will most likely make 'sound', right? So naturally it would be a good idea to give the guard some sense of sound. So if the player makes sound, the sound will get a x,y and a range value. If a guard is in that range value, it will come to look what happened, and than will spot you due the 'sight' he got before. This way, you will most likely have a more 'intiligent' enemy than you would have got if it was the 'same old' 'follow the pattern' ai.

I know it's a little hard to accomplish on a calc to give every enemy a 'good' AI. But it's fun to do, and I believe even more pleasing and suprising to see how the AI is working in different enviroments.

What are your experiences, thoughts and idea's about AI?
Image
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

I am yet to code any meaningful AI, but i have thought about it a bit. I really like your guard example, it reminds me of that game Commandos.

In my next project i hope to have a few classes of enemies. Ones that will chase after you if they 'see' you and stuff like that. Although i am not far enough along to worry about that stuff yet, i have been thinking about the implementation side of things.
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
VahnRPG
Extreme Poster
Posts: 331
Joined: Mon 20 Dec, 2004 10:44 pm
Location: Earth...currently...
Contact:

Post by VahnRPG »

I, too, have yet to ever create anything meaningfull
In my games, the most AI i've had was the computer generating a random number and then doing an action corresponding to that number.
For BW-Q I'm thinking of making some premade patterns for each enemy, then having it choose a random pattern and probably a random number to dictate how many of that pattern to do...
I'd rather be a nobody remembered by someone than a somebody remembered by noone.

'Boku' can't save the world - Blaze Rennaul
--'Boku' doesn't have to... - Klyne Ryuuno
Blue World - Coming soon
Kozak
Maxcoderz Staff
Posts: 791
Joined: Fri 17 Dec, 2004 5:33 pm
Location: On the dark side of the moon.
Contact:

Post by Kozak »

I've never used real AI.

For TVF: Enemies choose a random between 2 and 0 to determine who they are going to attack (not even a choose the weakest technique :)).
For paratroopers: No AI at all. Troopers make a tower by storing a state in which they are in and incrementing the state untill the tower is build.

For my UOH (uniform object handler) I thought of a way to handle characters on screen. I had a general update loop which checked what input the character got:
- player input character, check for keypresses (so I could have 10+ character controlled chars)
- inverse player movement (same as player movement only inverse, also seen in zelda)
- random direction (enemies choose a random direction which they walk for 3 secs and then evaluate again)
- pattern (store a pattern which they walk)
- follow player (move in direction of player)

So here, no real AI either. But I can imagine how cool stuff like that can turn out.
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version
User avatar
blueskies
Calc Wizard
Posts: 553
Joined: Tue 25 Apr, 2006 2:24 pm

Post by blueskies »

I think one of the main features should be variety. It's nice to have different actions or speeds for different enemies. I like idea vincent about a guard's sight and sound region. You could even have different levels of alert. If he hears something, alert level 1, he goes and searches the area the sound came from. If he finds nothing, back to level 0 alert (patrol). If he finds a body, alert level 1, he searches a larger area and calls more guards. If he finds you, alert level 2, attack. This is basically the way Metal Gear Solid works, but it could be a lot simpler for the calc.

One thing that kind of stumps me is the AI for an enemy to manuever around objects. It would be easy to have the guard run straight towards your (x,y) position, but what if he runs into a wall or a tree? I think in the top view zelda games, the guards would just hit the tree, then move left or right until the could move down again (or up/down until they could move right again...etc). Is there a good method for doing a pathfinding routine?
Stickmanofdoom
Regular Member
Posts: 86
Joined: Fri 17 Dec, 2004 8:20 pm
Contact:

Post by Stickmanofdoom »

Don't ask me how this works, I just did a google search for pathfinding and found this site. It talks about the A* pathfinding algorithem (apparently the most popular) and also has links to other various links about A* pathfinding. Of course this would(?) make the enemy move directly towards you but there are probably some variables you could change to make them less than perfect.
AI is a problem I am going to have to address for the game I am working on. However, I don't think a platformer with bots would use the same algorithem.
User avatar
VahnRPG
Extreme Poster
Posts: 331
Joined: Mon 20 Dec, 2004 10:44 pm
Location: Earth...currently...
Contact:

Post by VahnRPG »

I'm actually kinda afraid of making AI...mostly because I'm worried I'm gonna make something REALLY AI that'll end up taking over the entire world >.<
I'd rather be a nobody remembered by someone than a somebody remembered by noone.

'Boku' can't save the world - Blaze Rennaul
--'Boku' doesn't have to... - Klyne Ryuuno
Blue World - Coming soon
User avatar
blueskies
Calc Wizard
Posts: 553
Joined: Tue 25 Apr, 2006 2:24 pm

Post by blueskies »

haha...hahaha...a calculator on a rampage to find the most efficient route to Link. :D
merthsoft
Extreme Poster
Posts: 496
Joined: Tue 21 Dec, 2004 6:49 am
Location: WI

Post by merthsoft »

tr1p, your ideas are very similar to that of Wolfenstein-3D (by id...). Basically, they had teh playerpos_x and playerpos_y, and then they had facing_dir (direction the guard is facing), and guard_x and guard_y, and lets say the player is south of the guard, and the guard is facing south, they would have a certain angle in which the guard was facing, and if the player_x and player_y were in this angle, he would make a sound, and alert (it's been a while since I messed with their source...).
The sound worked very similar to how you described too. The maps had floor tiles for the floor where there wasn't an object or a wall, and if you shot your gun, then gamestate.madenoise would become true, and in every room filled with that floor tile the guards would be notified, and if you opened a door, and shot in the room connected through the door, it would work the same with, except with both floor tiles being alerted...
0000000000000000 a=floor tile a
0aaaaa0bbbbb0aa0 b=floor tile b
0aaaaa`bbbbb`aa0 0=wall
0000000000000000 `=door
so if you are at the "a" in the upper left hand corner, and you shoot, then the third room gets notified, and if you open the door to the second room, and shoot, all three rooms, and any other a's and b's will be notified...
Sorry for the long explanation, maybe it'll help some people out...

Note: gamestate.madenoise would become false after so many ticks...
Shaun
teoryn
New Member
Posts: 26
Joined: Sat 18 Dec, 2004 4:23 am
Location: Ohio
Contact:

Post by teoryn »

AI is a rather intersting subject, great that you bring it up.

As for myself, the most AI I've done is in my pong entry to the mcz competition, and all it would do was compare a random number to the diffiuclty level and if successful would move towards the ball, otherwise away/stay still. It managed to work well, and was simple enough to help keep the size down.

In the future I'd like to play with neural networks some, but that would require quite some more experiece then I've got right now.
You've seen the posts, now see the sites!
http://hiddenuniverse.blogspot.com
http://teoryn.deviantart.com
User avatar
Dwedit
Maxcoderz Staff
Posts: 579
Joined: Wed 15 Dec, 2004 6:06 am
Location: Chicago!
Contact:

Post by Dwedit »

The kind of AI I'd use would be mostly pathfinding algorithms to find what route to take to get from point A to point B in a map with walls.

If you're making a board game, looking ahead at all possible moves and scoring the consequences for 4 look aheads would cream most human opponents. The time it takes grows exponentially with the look ahead depth, so you would need to trim away some things that would come after bad moves.
You know your hexadecimal output routine is broken when it displays the character 'G'.
User avatar
GuillaumeH
Regular Member
Posts: 143
Joined: Fri 17 Dec, 2004 8:30 pm
Contact:

Post by GuillaumeH »

In zDoom 0.09, the AI is simple. Enemies are by default in an "idle" state. When the player sees an enemy and comes near from it, the enemy's state switches to "attacking", and then the enemy moves towards the player and frequently attacks. That's all.
Kozak
Maxcoderz Staff
Posts: 791
Joined: Fri 17 Dec, 2004 5:33 pm
Location: On the dark side of the moon.
Contact:

Post by Kozak »

A while back I did some research on AI pathfinding for a strategy game I wanted to make. Then I only came up with 2 solutions which can fit a calculator:
- A*
- hierarchical beacons
The last one I thought up myself but sadly it already existed :'(.

First about A*. It uses a simple calculation mechanism so we don't have to worry about that. It does need a data storage area as big as the map (since it needs to store which one it already checked and some other value).
Problem with A* is that it will take CPU time, the bigger the map the more. Theoretically it could check every tile in the map to see if it can go from A to B. And it needs to reevaluate it's route every time point B changes position.

Hierarchical beacons.
Here you place one node on the middle of the map. Then you let other nodes branche from that in a way that the path between those nodes doesn't have any obstacles. Now you branch more so the whole map is covered (not to much nodes though, since that'll data and speed eating).

Now when you want to go from A to B you first manhattan the distance between A and all the nodes on the map the between B and the nodes. Then you trace back trough the tree untill the nodes have the same parents: you have a path.

This method is fastest but isn't as accurate as A*.
==============================================
Conclusion
On small maps use A* since it's accurate, still pretty fast.
On large maps use hierarchical beacons.
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version
Kozak
Maxcoderz Staff
Posts: 791
Joined: Fri 17 Dec, 2004 5:33 pm
Location: On the dark side of the moon.
Contact:

Post by Kozak »

BTW in maxpayne it's also pretty basic.

For pathfinding the have a pre calculated AI node network.
For AI they have standard state (aggresive, moderate etc, cover combat).
A state can be activated by feeling seeing and hearing, and those values can be modded into eternity.
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

Have you had a chance to study the AI in Half-Life 2?
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
Post Reply