[ODE] OT: virtual creatures in games

[david@csworkbench.com]

I'd love to add some input to this discussion, since I plan to eventually
do something somewhat similar.

I don't think you necessarily want to evolve the locomotion of the
"creatures" in your world, but rather, you want to evolve the state
machine itself that determines what their next move will be.  For example,
if your creatures have the ability to move, then the an output of the
genetic algorithm / neural network would be which direction and how fast,
not necessarily what angle the knee joint needs to be, and the actual
method of movement would be hard coded.

Assuming that's what you mean, then there are a few things that any
evolutionary algorithm would need to display any type of "intelligence". 
Most paramount is a fitness function.  Since it doesn't sound like your
game is primarily hostile, amount of time it remains alive may not be a
great factor.  Perhaps if your creatures were in competition with people
for the same thing, you could have some really interesting behaviors
evolve.  Not knowing much more about your game, I can only assume that
there is a challenge to the humans other than these creatures alone.  More
than likely, your fitness function will be a weighted sum of many factors,
and you could even use a larger genetic algorithm to optimize these
weights for the number of man-hours people spent in your game :)

Ok, let's assume you have a function now that differentiates a more
intelligent creature from a dumber one.  Now all you need is a set of
actions this creature is able to perform.  It can be as simple as just
walking/running speed and direction, and whatever their attack method is
(bite, breathe fire, shoot, etc.) or you can add in more complex actions
like howling, jumping, eating, growling, sitting, ducking, or whatever
else you feel like implementing.  You would probably want to give them
enough skills that there would be many ways to get high fitness values. 
Just remember, you need graphical transitions between every skill (or just
make every skill start and end in the same position.... might not look as
good).  With this method, you would have to write absolutely no AI other
than the genetic algorithm itself.  There would be no variation in how
creatures looked as they do stuff, but their behaviors would be totally
random, and hopefully they would become better at acheiving their goals as
defined by the fitness function as the game progressed.

Every time a new creature is spawned, create it with a new brain (I would
suggest a genetic program over a neural network, as each node is more
expressive, i.e. more intelligence for less calculation).  Since you would
only be selecting and crossing over when new creatures were spawned, that
would be the limiting factor in how much you could do with this.  If your
game is like Everquest, where the primary purpose of the creatures is to
provide targets for the players, any genetic algorithm may be
prohibitively expensive, assuming you do the selection and mutation step
on the server.  However, if you made it the job of the client to do those
steps, then you are practically unlimited in what you can do, since the
client would select a new brain for the next creature to spawn every time
they killed one.  You could upload your top 10 brains and download a new
gene pool every 30 minutes or so.

On the other hand, if your game isn't combat oriented (or the creatures
aren't involved in the combat very often) then another goal will have to
be given to creatures.  i.e. a genetic algorithm without a goal will
probably get really good at.... doing nothing.  If you're just looking for
different behavior out of each creature, pure randomization may be all you
need.  You could still use a neural network or function tree as your
medium, just not worry about gene pools and selection/crossover/mutation
methods.

In summary, any 'learning' algorithm is going to totally depend on your
ability to programatically tell the difference between a smart and dumb
creature.  If you can provide that much, then you have quite a few methods
of creating smart creatures.  Tell us (or email me personally) some more
about your world and the role you want the creatures to have in it and
I'll probably have another pile of ideas to throw at you :)

I eventually hope to create a distributed world on the internet that may
or may not have any human interaction, where the creatures evolve in an
environment where they are competing for a limited supply of energy.  I'll
include stuff like inter-creature communication and the ability to decide
(through genetically determined parameters) how much of your energy you
spend on moving, sensing, even thinking (bigger brains cost more energy). 
It should be interesting to see if creatures evolve into cultures of
separate brains and brawns, or if it turns into an everyone for himself
kind of world.  But I've got to have a fast physics engine first to
simulate worlds of the size and scope I hope to acheive :)  I've got a
simple Function tree style brain class lying around somewhere if you'd
like to take a look at it, but I'm seriously considering learning and
moving to Python to allow myself more time thinking about actual
algorithms and less worrying about memory management and all the other
baggage C++ has.... and Python has a built-in Code Object.  Not sure if I
can take the performance hit, though.

David

>
> BTW, just to clarify, I'm ideally interested in neural net type
> learning, rather than hardcoded approaches like path finding - hence my
> question here. The exciting thing is not being able to predict how a
> creature might learn to achieve it's motivations...
> --
> gl
>
> ----- Original Message -----
> From: "gl" <gl@ntlworld.com>
> To: <ode@q12.org>
> Sent: Wednesday, March 26, 2003 12:26 AM
> Subject: Re: [ODE] OT: virtual creatures in games
>
>
>>
>> Interesting - I guess I should classify what I'm after.
>>
>> Essentially I'd want creatures for an on-line world that do
>> unspecified interesting things using some believable motivation, and
>> some would be potentially hostile.  However, gameplay would not center
>> around them (and there would no need for predicatble outcomes) - it's
>> more about having interesting, unpredicatble and potentially dangerous
>> things to explore,
> all
>> as part of a much larger landscape.  The creatures may themselves be
>> randomised to some extent, depending which way I end up taking this.
>>
>> The idea is that the game is not only different every time, but I also
> want
>> my own creation to suprise me.
>>
>> As this is a persistent online world, it would also be fun (if
>> feasible)
> to
>> evolve creatures over time, or at least keep them learning and
> experimenting
>> with their environments.
>>
>> As for inputs, I would have things like raycasting, light sensivity
>> (if I can figure out a fast way), perhaps smell, memory of other
>> creature types/individuals (eg. a creature could learn to become
>> hostile to
> player(s)
>> if they treat them badly, or run scared etc), and possibly things like
>> memory of areas that are safe (hiding under a rock) - that kind of
>> thing.
>>
>> So, can anybody recommend an AI approach that fits the bill without
>> huge performance/memory requirements (memory because I'd want a lot of
>> these,
> and
>> it might eventually be a console game too)?
>> --
>> gl
>>
>> ----- Original Message -----
>> From: "John DeWeese" <deweese@ict.usc.edu>
>> To: <ode@q12.org>
>> Sent: Tuesday, March 25, 2003 11:54 PM
>> Subject: Re: [ODE] OT: virtual creatures in games
>>
>>
>> > I've had a few thoughts about this which might be fun to share.
>> First of all, you have to ask what kind of game you want to make,
>> but given that simulating an articulated creature takes a lot of
>> investment in programming time and run-time computing, it is likely
>> to be a primary feature of the game. If you have enough computing
>> power, you can make it secondary and special-effects related if you
>> so desire.
>> >
>> > Problem the first: traditional AI algorithms for path planning,
>> decision making, etc. assume that the unit being controlled behaves
>> predictably, i.e. that it will trivially (perhaps eventually)
>> converge on a state, or die trying. Bad AI happens when the units
>> get stuck, or start moving somewhere wierd like a live fire zone,
>> but it's worse when you can't even guarantee if you virtual creature
>> can move where a high level planner wants it to move. If you cannot
>> guarantee this of your virtual creatures, you must limit their role
>> to playthings (as in an exploration or toy game) or special effects.
>> On the other hand, it would be very nifty to develop a framework
>> which allows you to make some statements about what conditions are
>> necessary for convergence (e.g. moving to a target) or divergence of
>> a given creature. There may be some research on this out on the web.
>> Karl Sims had a video of a little swimmy thing following a point,
>> and it would follow it pretty well. If you've got some consistent
>> directed locomotion, I believe you can start to design some
>> meaningful higher level AI.
>> >
>> > One BAD thing to do would be to place the user in direct control of
>> the creature, as in Quake... unless you can make some guarantees
>> that the creature will do PRECISELY what the user expects when he or
>> she expects it, which is difficult. You may have to come up with a
>> hybrid kind of scheme, with some direct control and some implicit
>> simulated control.
>> >
>> > What happens if you want to evolve the creature in-game? Well, lots
>> and lots of waiting for one. Boring! That is, unless it's a
>> "digipet" kind of game, which has different requirements.
>> >
>> > Regarding resource usage, you'll have to time it yourself according
>> to the kind of creatures you have running around! This very much
>> depends on your specific code. Very jointed creatures are a waste,
>> of course. Neural networks should be pretty cheap if you keep the
>> node count low, and most virtual creature projects have relatively
>> small neural networks, on the order of 10 to 100. Memory is cheap!
>> >
>> > Finally, lack of control of basic gameplay principles like movement
>> (as I mentioned before) generates big problems for a game designer
>> setting challenges for a player. Often in a game you want to advance
>> the state of a story or something of the sort, and in order to
>> advance you require that the player accomplish some goal or solve a
>> problem using a skill. If the player operates on different rules of
>> movement or interaction than your assumptions, you as the designer
>> will no longer have control over how the player is rewarded
>> regarding goals and stories! If you require the player to evolve
>> creatures for every task, this is expensive and the player will have
>> difficulty exploring the space of what each creature can do. This
>> might not even be a bad thing, but it is at least LOTS more
>> difficult if you can't consistently teach all players a skill! This
>> topic needs more discussion, though, since you may very well come up
>> with a method to solve this problem or make it irrelevant and still
>> make a game fun.
>> >
>> > Sorry for the long post...
>> >    John DeWeese
>> >
>> > On Tuesday, March 25, 2003, at 12:13 PM, gl wrote:
>> >
>> > >
>> > > Sorry for the (sorta) OT post, I promise it's a one off, but I
>> know there's
>> > > a lot of people here that have worked on virtual creatures.
>> > >
>> > > Without having done any work in AI (though I understand some of
>> the principles behind neural nets in general), I'm wondering how
>> feasible simple
>> > > learning creatures and/or fully evolved creatures are for use in a
> real
>> > > game.
>> > >
>> > > Using the simple creatures that learn to walk/crawl/jump as an
>> example, how
>> > > heavy are they on system resources (both memory & CPU)?  I'm
>> really asking
>> > > about two cases:
>> > >
>> > > a) where you have evolved a creature in a seperate app to a
>> sufficient level
>> > > of intelligence, and just want to use its brain as is in a game,
>> without
>> > > further learning ability - how much memory would its brain take up
>> (roughly), and how CPU heavy would a logic tick be?
>> > >
>> > > b) where you want the creature to continue learning in-game to
>> make
> its
>> > > behaviour more interesting and unpredictable.  Again, what are the
>> resource
>> > > drains?
>> > >
>> > > I'm only after very rough guides - any insight would be
>> appreciated. --
>> > > gl
>> > >
>> > > _______________________________________________
>> > > ODE mailing list
>> > > ODE@q12.org
>> > > http://q12.org/mailman/listinfo/ode
>> >
>> > _______________________________________________
>> > ODE mailing list
>> > ODE@q12.org
>> > http://q12.org/mailman/listinfo/ode
>> >
>>
>
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode