[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 947
  • Last Modified:

2D Fighters - AI Techniques

Hello,

I've been programming for a few years now, and have only recently decided to do much Game Development. I have created simple games like Pong, etc, no problem at all; I am now planning to develop a slightly more advanced (and more graphic) game.

My plans are to create a game, similar to the classic "Streets of Rage 2" (originally on the SEGA Megadrive) - for a screenshot of the game, see here: http://www.emulationgalaxy.co.yu/images/Streets%20of%20Rage%202%201.gif

I've worked most of it out, however, I'm looking for tips on the AI Development, of the 'bad guys'. I would just make some things up myself, but the most advanced AI that I've created for a game, is in Pong! lol (and that's about as simple as it gets).

Also, I'm looking for the most efficient AI techniques here -- keeping in mind that I'm developing this game in Java, which is not the fastest language (although, it is "considerably" fast). For those familiar with the Graphics of Java, I've already sorted out the laggy/flickery display, by implementing a custom Double-Buffering system .. which works a treat :-)

I just need help with these bad guys!    ^_^

Thanks in advance,
Rob.

P.S. I believe that I actually need to express the characters/objects position in 3D; so, please keep that in mind, if it's any realy significance to the asnwer that you'll provide. :-)

0
InteractiveMind
Asked:
InteractiveMind
  • 8
  • 6
  • 6
2 Solutions
 
softplusCommented:
Hi Rob
IANAGP (I am not a game programmer), but my 2cents (having done bits with real AI):
- Don't get into AI just for a game. AI is a very large area, includes lots of higher math. Using real AI in a game environment would probably be a waste of time (processing time and programming time), especially if you're doing this by yourself (i.e. not in a team)
- Think simple, think fast processing: (B = AI bad guy, P=Player)
.. P stands still: B goes to P - speed is based on a player-code, i.e some players fast, some slow, use random functions
.. B close to P: B hits P - hit type based on skill-code for player + random functions
.. P hitting on B: B backs away OR B hits harder on P (based on skill-code + random)
.. P far away: B does funny stuff, sticks tounge out, jumps, etc. based on random + character-code

Using things like this you can set up a very cheap, simple pseudo-AI type system, where the B acts upon certain catagories of activity / location of your P. Using random functions it won't always be the same action. Using codes for the B (speed-code, skill-code, character-code) you can give your characters a personal look, i.e. have a "funny, fast, weak" guy, a "serious, slow, strong" gut. These simple rules will be easy to expand and they hardly require processing power (whereas real AI is processor hungry, needs to "learn" action/reaction, etc.).

John
0
 
InteractiveMindAuthor Commented:
Thank you very much, John.  :-)
That helps; I will leave this thread open a little longer, to see what everyone else thinks also.

Regards;
Rob.
0
 
softplusCommented:
You can use these types of rules to create a type of fuzzy logic for certain actions:
i.e. Hit player or not?

value = A * distance + B * current-strength + C * skillindex * rnd + D * P-is-hitting-me  + ...

you just need to define your A,B,C,D, etc. with a fix number, play with a rule like this in excel and then create a threshold, i.e "start hitting if value > 100".

Doing it like that helps save you from long spaghetti-code (lots of if's, etc.). If you create reasonably large factors for that, you can make the influence of the components stronger or weaker (i.e. here A = -50 --> the other factors have to overrule this to still reach the threshold of 100). You just need to evaluate this one function every time the player comes up and then you "know" to start hitting or not (hitting = any action :)).

Add to that a simple state machine, i.e. change your factors based on the current state, say "B hitting on P", "B away from P". Change states based on simple rules: i.e. in "B away from P"-- if distance < 1, change to "B hitting on P".

Does that make any sense? We did this type of stuff in our small autonomous robots (no not the hitting, but similar algorithms). fun stuff :))
John
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
InteractiveMindAuthor Commented:
Sounds good :-)

That answers all questions I had .. points are yours! ^_^

Thank you John.
Rob.
0
 
Sergio_HdezCommented:
I agree with softplus, like we say in spain, don't kill flies with cannons!

I would use some few values to determine a "bad guy" movements:

A) Is player behind you? Turn around.
B) Is there any enemy (except you) blocking your way (in left-right direction) to him? Walk up/down so you are not aligned with player nor whith other enemies between you and player so can bypass the others "bad guy". (up/down could be decided just comparing vertical space under and up the player: if the player is in the upper half of the screen, try bypassing enemies going down, other wise, go up)
D) If B) was negative (you are clear to walk to the player if you were at his same level), then walk up/down to the same level as player is.
E) In this point, preferred level is determined, so only need to determine if at current level (may be you still had to move to get to the desired level) you can take a step towards player if no one is just is in front of you.

Those rules will make player atract bad ways in a nice way, but still can be improved...

1) If enemy is at your left, then you left-right desired point is not the player position, but some inches in front of him, so if some how you manage to be placed just over the player, you will tend to go a little away from him (left-right direction) and then you will be able to go down to his level to fight. If you always intend to be on his X position, you will get stuck over him without fighting.

2) If many enemies block you "natural way" to the player, a flag could be used to change move rules to other ones in the fashion "go away from nearest enemies before trying to get to the player" that could be using for 2 or 3 seconds.

Well, you can try those rules and then pulish them in order to make playing more pleasant or realistic, but you wouldn't need to more complex approaches to the AI I think.
0
 
InteractiveMindAuthor Commented:
Sergio_Hdez,

Excellent .. that is also useful  :-)  Thank you!

Rob.
0
 
Sergio_HdezCommented:
Another eficient and self-learning solution (I like this idea, sound very promissing):

Use a simple neuronal network (don't panic, simple ones are very easy to code and to use) that get as inputs the positions (relatives to you) of the other enemies plus the position of player, this last one with a higher weigth (a stronger "signal" is sended to the neurons connected to this position), then let the neuronal network to work (it is very computer friendly) and get 2 outputs, each of them of 2 bits, and meaning go up, down or stay (the 4th posible output of a 2 bits number just means "do nothing", so 2 of the outputs means "do nothing").

Then, if after 5 or 10 more steps you are nearest, the net worked well, if don't -you may be dead also- this was a bad suggestion, so the net is reprogramed to avoid this output again in similar conditions. So at each step, you have to compare actual position with the one you had 4 steps before, and if it is not nearest, punish this decision. Then make a new decision (step) and store it in a historial (you need to store the 10 last decisions in order to determine later if it was a good or bad idea).

Well, programing it is simple, neuroanl networks, in this level, are just pipe-lined nodes layered: Initial ones, in first layer, get fired if an enemy is in this position -like conected to small squares in the floor- then the fired ones pass it to the nodes in next layer that are connected to it -you have to decide with ones connect to with at coding time, usually the layer go from wider to narrawer layers, so at the end you have only 4 nodes, that represent the 4 bits you need as output-

Once a node recieve inputs from layer over it, you compute the total amount of "energy" coming into the neuron, and if it is more than a given number, if fires and send a signal to the next layer.

The strenght of the signal sended from one node to the other is what define the net usefullnes, is like havig a thin or fat wire connecting them, or a pipe line, so storing those "wieghts" of the connections gives you an snap shot of the net at this moment.

The learning is easy: If after 10 steps you decide the position is worst (using usual programing), then you have to avoid the output you got: Determine witch pipes transmited energy on that step (you can store this list only on every step) and make all them 10% smaller (so they transmit 90% of the energy they used to).

After some time, the enemies "learn" to fight: The size of the pipes of it's neuronal network adjust them self with this trial-error system so the probability of getting better position in the fight is higher.

The problem here is how to determine if actual position is better than the one you had 10 steps before: If being dead now is much worst, then the IA will avoid it, and you will breed cowards! So be dead is not so bad for a bad guy, they always die!

Well, this is just an idea, but having learning capabilities is a good adition to any IA, and coding is aesy and fast for the CPU. Imagine the bad guys learning to avoid your best tricks! Or learning not to follow you if other enemy is blocking, or learning to wait for other "friends" to come before attacking you... sounds nice!
0
 
InteractiveMindAuthor Commented:
Sergio_Hdez,

that is all fantastic, but I'm afraid that neural networks are a little over my head at the moment :-(
I'm sure that I'll try my hardest to implement them into my next game though!  ^_^

Thank you very much.
0
 
softplusCommented:
Good idea sergio :) - but it's not fun if the bad guys learn how to beat you faster than you learn how to beat them :)). You could pre-learn them though, i.e. save the neural network settings after training with 10-20 games for the easy setting, after 1000-2000 games for the expert setting :). Neural networks are fun :))
0
 
Sergio_HdezCommented:
Yes, and all bad guys of the same type could use the same net, so if you decide to make them learn, all them will increase "eficiency" at the same time... also you could "mix" two nets (averaging values) to get a new character... a lot of possibilities!

Another one: Why don't you "especulate" with a net about what would you do if you (the program) where the player? If it doesn't fit, re-learn, so after watching a player play for some minutes, you have a net that have silently learned all your tricks and behavior, so the "final bad guy" of the level could be a clone of your own player! It would make the final stage VERY challenging: The worst you played the level, the easier the final guy is.

Another idea: Store the neural net that imitate the player in the high score tables, so you can decide to play agains "the player that is 1st in the top score table", or even make a match where to "real player" are imitated in a PC vs PC fight! This one is the best possibility! Breed your own warrior by let him watch you play, then send it to a friend to see if it can defeat him or his own breeded warrior.

If I weren't against software patents, It would be a good idea to patent! (just joking)
0
 
Sergio_HdezCommented:
Interactivemind, I also thought all this stuff were very "academic", but it is VERY simple to program, I promisse. If you decide to make the take the steep, I can guide you a little, I did a small net to determine if a B&W hand made drawing was a circle or not, and it took me half an hour to do (in basic), and was my first and last attemp!

Basically, you only need two arrays: One of NODES[1..10, 1..100] (integers) where 1..10 is the layer where it is supposed to "be" the node (1 being the first one, connected to the portions of the floor). The other 1..100 elements represent each node at this level.

First level will have 100 nodes actives, while second one only a half, and so on until last level only have 2 nodes in use (we don't need 4 as I sais before, only 2: One for X axis, other for Y axis).

Each node just have to store it state: 1=one enemy on this place, avoid me, 0=no one here, -1=interesting place, go there to fight.

Now you need a second array, this time of floats: PIPE[layer1, node1, layer2, node2] that will have the size (width) of the pipe connecting two nodes. It is really up to the programmer to decide how much pipes to create, but connecting ALL nodes in a layer to each of the nodes in the next layer is a possible and simple approach.

OK, now the working: Fill all the nodes with state=0 (off) and all the pipes with the same with (1 for instance), now the net is clear like a new born.

At each step, put state=1 on all nodes in layer 1 that have an enemy on the square of terrain you have assigned to it (this have to be relative to you, so if one enemy is 3 steps to the left of you, and 1 to the top, this is the 2 numbers that determine in with node of the first layer he is standing).

If 2 enemies are in the same node, sum 1+1 and get state=2. Finally, in the place where the player is, put a -5 (in that idea, a 1 in the node means "avoid this place", while -1 means "try to go there to fight).

Once you fill the state on all nodes in the first layer (just do a for i=1 to enemy.count or similar, don't need to loop on all 100 nodes if only have 2 characters on screen), you need to iterate 9 times so the "signal" reach the next layers.

On each step, nodes on layer i+1 get "energy" from active nodes in layer i : If there is a pipe conecting a active node in layer i with a node in layer i+1, then sum to the state of this node the state of the node in layer i x pipe width. After all those sums, the nodes with a sum of energy > 2 (or other number, doesn't mind), fire, and get a state of 1, while the ones with energy < 2, get state -1. To simplify, you can use State=round(energy), so state can be also -2 or something similar.

After all this (very simple algorithm), you get the 2 nodes in last layer with a 1, 0 or a -1 (well, the may have a bigger number, but only it sgins is important at the end). So, you just move your enemy to the left (first node is in state < 0), right (first node is in state > 0). The same with up or down (look at second node).

If you decide (after N steps) that you are in a worst position, loop on all the pipes that transmited energy and make them smaller by something like PIPE[L1,N1,L2,N2]=PIPE[L1,N1,L2,N2]*0.9

Thats all, the learning machine is running! Just mention that the more complex the pipes are, the more time it takes to learn but the smarter the enemy can become, so adding more layers, or connecting a layer with nodes 2 or 3 layers up can improve the "learning curve" of the enemy.

OK, I stop writting here, too much literature!
0
 
softplusCommented:
Sergio, we should make a small expert machine to automatically answer easy EE questions :)). Good description for the neural network, but I think we're going over his head here :))) - maybe we should split the game and let Rob do the graphics and we do the Badguys :) - If I didn't already have negative time at the end of the day, it would be a fun exercise!
John
0
 
Sergio_HdezCommented:
Yes, I also have a "imaginary amount of free time"... I love sleeping a lot!
0
 
InteractiveMindAuthor Commented:
John's right that it's a little over my head.. still. :o\  lol ... I haven't even finished school yet, so neural networks require a bit more effort than trig, and pythagoras  lol  ^_^

I would love to see some very simple examples of such things with Neural Networks; I find that in many cases, when I'm working in regions that I'm unfamiliar with (in this case, NN's), I can pick it up a lot quicker after seeing examples. :-) Do any of you lot have any?

Thank you,
Rob.
0
 
softplusCommented:
Hi Rob
Actually, neural networks are probably easier to understand if you look at the theory behind them first. Just looking at the code will have you scratching your head, as the code is actually quite simple, but what it really does isn't so straight-forward. Let's see...

Try some of these links:
http://en.wikipedia.org/wiki/Artificial_neural_networks
http://www.cs.stir.ac.uk/~lss/NNIntro/InvSlides.html
http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html

You'll see it looks fairly complicated, but it really isn't, once you understand it :))). There are lots of things you can do with them, so the theory is fairly general.

John
0
 
Sergio_HdezCommented:
S   S   S   S
 \   |   |   /
  N N N N
   \ |   | /
    N   N
     \   /
       R

A simple example: Each letter in this graph is a neuron, it has an state: on or off, and each line represent an axon that connect a neuron with the neuron under it. Each of those lines has a capacity (from 0 to 1, for example). They act as tubes connecting neurons downwards: From 'S' to 'R' passing by the 'N' neurons.

The goal is to switch on some 'S' neurons (sensorial neuron, like pixels on a screen that can be black or white), let the signal travel down layer to layer using the tubes, and finally, look at the final state of last neuron 'R': On will mean something positive, off negative.

The funny thing is that a design like this can be "trained" to obtain any "answer" you want: on can mean "the drawing is almost black", or something more sophisticated like "lines in the drawing are more horizontal that vertical", or even "the drawing represent a human face".

How do you train it:

Initially, all connections have the same capacity, let say 1. Our goal is to find a set of capacities that, when you feed the sensorial neurons with a example, the tubes will "destille" the desired answer, whatever it is.

For doing that, you get a set of known examples, you know with answer they have to produce, so you give all those examples to the sensorial neurons, make it destille an answer, and if it doesn't fit your expectation, then "punish" all the tubes that carried energy by making its capacities a little smaller.

How to destille an answer:

Feed the sensorial neurons with an example by setting "on" the appropiate ones, and leting the other neurons in this and other layers "off".

Loop from 2nd layer down to last one, and in each loop, sum the "energy" that each neuron recieve from the upper layer: For each neuron in layer 2, search for connections coming from layer 1 and that comes from a "on" neuron ("off" neurons are discarted), and make the sumatory of the capacities of those "tubes", so you calculate the "amount of energy" hitting this neuron from its upper layer. If that sum is greater that 1, set the state to "on".

Finally, you have some neurons on and other off, but only last layer neurons ('R' in the drawing, can by one or several neurons depending on the complexity of the answer you spect. This example xpect a yes/no response, so only need one) are important: If it is "on", answer is "yes", other wise, answer in "no".

At this point neuronal net made its work. From here, your program can ask: "Answer is "YES"... was it correct?". If the answer is not, then search all tubes that start on a "on" neuron (the ones taht carried energy down) and make capacity=0.9*capacity, so the training is tweaked to better at each mistake you find.

After some time, the net will become more accurate, and if the complexity of the desing of the wirings is well dimensioned -you only know this by trying to teach it: If you fail, the net is way so simple for that- you will get a smart net finally.

As you see, programming it is simple, VERY simple, and the working is simple, just "destilling", the only magic is how such a simple approach can learn to recognize a scanned letter, for instance, as it does some OCR programs... this is amazing!

Other "simple to program, amazing to see what they can do" things are, for instance, Fractal images (Mandelbrot set is easy to program, imposible to explore), Fractal compression (look in google, it is also magic on this, a photo can be compressed in a way no zip or jpeg can dream on).

If others know similar jewels of algorithms, please post!
0
 
Sergio_HdezCommented:
Apadting the example to your case: Each 'S' neuron will be connected to a piece of floor in your scenario, if your enemy moves, the pieces of land moves with him, so same neuron is always referring to the same piece of floor RELATIVE to your enemy.

Now feed the net: Put to 'on' (value = 1) each 'S' neuron with an enemy on it. Two enemies will put a value of '2' to the state (here state is an integer value instead of a boolean value like in the example). Finally, if the player is on a 'S' floor piece, make its state -5.

Now you have all the sensorial neurons loaded with the snapshoot of the scenario: Let it destille a result in last neuron. This neuron will be finally on state '0' (don't move), '1' (move to the right) or -1 (move to the left). States like +2 can be treated like +1, or you can make the enemy move quicklier, it is up to you.

Finally, if you make the last layer with 2 'R' neurons, the other one can destille the up or down direction.

For training, you can play the enemy with the keyboard for a while, at each step compare your keypress with the one suggested by the net, and if they are different, re educate the net.

NOTE: Computer is faster than keyboard, so make the comparation each half second or so: If the key suggested have not been pressed in the following half second, it was a bad suggestion.
0
 
InteractiveMindAuthor Commented:
Sergio,

thank you very much for the explanation; I'm still having slight difficulty here. I think that I'm starting to understand the concepts of it .. however, I don't understand it well enough to program it yet. The main issue that I'm having with understanding it, is (back to your example):

S   S   S   S
 \   |   |   /
  N N N N
   \ |   | /
    N   N
     \   /
       R

 (i) Would I set all of the neuron's capacities to 1 at first?
 (ii) How do I then decide what value should be outputted from each Neuron (based on the input data, and it's capacity)?

Thank you very much -- and sorry about the delay; I've been waiting until I can spare long enough to read all of that (and take as much of it in as possible).

:-)

Rob.
0
 
softplusCommented:
I hope I don't confuse you; Sergio, if I'm not heading in your direction, just let me know :))

Another link for your collection: ftp://ftp.sas.com/pub/neural/FAQ.html

You have your inputs S and the output R, along with the layers of N in between, like you showed. Almost like you showed: the way I remember it, each node has inputs from ALL lower level nodes (or inputs), i.e. the first row of N's has inputs from all S's, not just one.

Each line between two elements has a "weight-factor" - this is what your system will be learning.

The output of any N is defined as:
  Output = some_function( Input1*Weight1 + Input2*Weight2 + Input3*Weight3 + ...)
so you're really just multiplying the inputs by their respective weights and plugging it into the function.

The function is usually a sigmoid function ( http://en.wikipedia.org/wiki/Logistic_function ), which means it goes from -1 to +1, with a "gentle" step around 0 where it switches from -1 to +1 - so values in the minus end up as -1, postive values end up as +1, values close to 0 end up somewhere in between. (1 / (1+e^-x)  is mentioned in the wikipedia, I don't remember what we used, probably that or an approximation).

So you see each node is taking all it's inputs, weighing them, adding them together and passing them through their function. In the last node, assuming you have only one output node, it will then give you either +1, -1 or something inbetween. You can use several output nodes to get more information (either for different "questions" or to add up for the same question).

To train the network, we mainly used "back-propogation". That is, you give the network feedback if it's answer was good or not. This can be done directly (i.e. nope, bad, try again) or in batch (i.e. you have a large collection of inputs and their required outputs -> have the network learn from that). To quote wikipedia: "By various techniques the error is then fed back through the network. Using this information, the algorithm adjusts the weights of each connection in order to reduce the value of the error function by some small amount. After repeating this process for a sufficiently large number of training cycles the network will usually converge to some state where the error of the calculations is small." I don't recall how we did that; in effect it would adjust the weights of each connection slightly each time. ( http://en.wikipedia.org/wiki/Back-propagation )

What you want to aim for is "Generalisation", in other words, you want your network to respond correctly to input it hasn't specifically learned. Knowing what to do if the player does the same thing over and over again is "pretty easy", but applying that "knowledge" to a completely new situation is also important (within justifiable range, of course).

Hope that helped :) Once you understand it, it's not really that tough; but it takes a bit to get there :)))
0
 
Sergio_HdezCommented:
softplus
---------
I agree 100% with your anotations, I just made it the most simple I could and avoided details that can make the net work more like a real brain. Well, ok, I admiti it, some of the things you mention are new to me... I just have the global idea of a neuronal network, haven't worked on it.



Interactivemind
------------------
(i) Would I set all of the neuron's capacities to 1 at first?

Neurons have a "state" that have to be set to 0 or OFF before each use of the net. Some sophisticated models could put a timer on the neurons so they switch off automatically after some time of not receiving singals or similar, but in the example it is you who reset it before filling the inpunt signal into the S neurons.

"Capacities" are not in the neurons, but in the conduits that connect them (axons in nature). They start having all the same capacity, but as the net is trained, they change and this set of final capacities is what you have to store some place to restore the net to its "learned" stated each time you want to use it.

(ii) How do I then decide what value should be outputted from each Neuron (based on the input data, and it's capacity)?
The output is always 1, but this output will reach several neurons, and each neuron will be reached trough a axon (pipe, conduit, etc) with a different weight (capacity, width, diameter...), so the 1 unit output will be received at each neuron with a diffrent strenght.

Those strength are the ones that you sum at each neorun (or use a more sophisticated sum function as pointed by softplus) to decide if it will fire or not.

Hope you have a clearer view after this pair of post. Feel free to ask more, no point needed on my side!
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

  • 8
  • 6
  • 6
Tackle projects and never again get stuck behind a technical roadblock.
Join Now