glob2-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[glob2-devel] Creature AI


From: Andrew Sayers
Subject: [glob2-devel] Creature AI
Date: Fri, 20 May 2005 08:11:04 +0100
User-agent: Mutt/1.5.9i

Hi,

This is rather a long and ambitious post, so get a cup of tea or
something before reading it.

I started playing Globulation 2 a week ago (getting into Debian is a
good source of advertising for you guys ;).  I really like the game,
but like all these sorts of games, I found the AI for the individual
globules (not AINumbi/AICastor etc., workers and warriors and things)
quite irritating, and I'd like to fix it.  Having looked around the
boards, there's a number of problems with the game (and new features)
I think I could do at the same time.  However, this would mean moving
Globulation in a different direction to where it's going today, so I'm
not sure whether you'd be interested.

Before I get started listing ideas, I have to be a bit stern for a
minute: my interest is strictly in improving globule's AI.  I'm quite
happy to talk about things I can put in as side-issues to that, or to
take out things you think would be a mistake, but I wouldn't be able
to motivate myself to get involved with other aspects of the game.  If
you're not interested in what I've got to say at all - no hard
feelings, I'll just get back to playing the game instead of talking
about it :)

For example, people have talked on the forum about growing resources
with gardens.  I would quite like to make this a simple creature
action (i.e. planting resources in empty spaces).  If you don't agree
- fair enough, I won't put that action in.  But you'll need to get
someone else to add that particular feature to the game.

__ Overview __

I would like to use genetic algorithms to evolve glob AI.  For those
that don't know, genetic algorithms find solutions to a problem by
using survival of the fittest: you start off with a random selection
of algorithms (which are inevitably rubbish), then throw away the
worst ones and fiddle with the best ones, until good algorithms start
to appear.

GA is quite a complex subject (and I only have quite a basic grasp of
it - if anyone knows any better, I'd be glad of your input!), but the
basic things you need for it are a "fitness measure" (a way of scoring
how good different algorithms are), and a way of encoding genes.
Working out the fitness measure for Globulation would be really
difficult, and I'd need a lot of help with the details.  Where I talk
below about giving "points" and "rewards" and things to globs, I'm
talking about the fitness measure.  Working out how to encode genes
wouldn't be too impossible, but I would need to redo a lot of things to
be more GA-friendly.

It's easy to think of this as a "magic" solution to the problem - it's
not.  I don't know if it'll work, and I certainly don't know whether
*I* can make it work.

__ Cons __

* The game changes direction, becoming focused much more around the
intricacies of growing a colony.

* I'd demand quite a bit of developer time.  I'd only be doing this on
the weekends, but I'd still need to ask lots of questions of people

* Harder to control units - e.g. you can only encourage them away from
  forbidden areas and towards war flags with rewards and punishments,
  not force them to do what you want.

* Globules might behave in irritating ways (like not admitting where
  they're going to until they get there)

* I might go around putting everyone's nose out of joint, then produce
  nothing.

__ Pro __

* Significantly better AI

* Whole new dimension to the game - the storyline could begin with the
  original creation of the globule race, and develop as the creatures
  evolve

* Multi-player games become more interesting - your globules can win by
  being smart, and might change behaviour during a game based on the
  behaviour of enemies.

* different unit types (perhaps - see below).

__ How Globules would act __

I must admit I have only a basic grasp of how globules work right now,
but at any rate I'd need to change it to make it easier to work with a
genetic algorithm.  The basic question is: what is the set of actions
a globule must be able to perform?  Ignoring for now "thinking"
actions - finding the shortest path to a resource, checking whether
you're hurt or hungry, etc., I've made up a list of actions a globule
can take.  If you're of a binary mindset, you might notice how this
set of actions maps quite neatly into one byte of data.

Each turn, globules can perform at most one action on a square adjacent
to the globule.  Some combinations of action don't work.  It will try a
specified action in either one or two directions, then move on to the
next action.  If no action succeeds, the globule does nothing for one
round.

The glob can request to move up, down, left, and right.
If the glob requests no direction, it stays still, and any action is
performed on itself.
If the glob requests every direction, it attempts to land or take off,
and any action is performed on itself
If the glob requests two opposing directions. it doesn't move at all
across that axis.

Globules can choose which (if any) actions to attempt, but must attempt
each action in the same order.  The four basic actions are:

* Go to
* Give/take (depending on whether you are carrying a resource)
* Attack
* Push

There are four things you can act on: buildings, other globules,
resources and ground.  Globules are allowed to attack friendly globules,
repair enemy buildings, etc. if they really want to (but these
behaviours *should* be evolved away).  Acting on sea if you can't swim
(or land if you can't walk) fails.  Possible actions are:

* Go to a building (walks into it)
* Go to a another globule (fails)
* Go to a resource (fails)
* Go to the ground (goes to it)

* Take from a building (go to it)
* Take from another globule (fails)
* Take from a resource (gather)
* Take from the ground (go to it)

* Give a resource to a building (build/repair it)
* Give a resource to a globule (repair/feed it if carrying wheat, fails
  otherwise)
* Give a resource to a resource
  (top up the resource by one point if they're of the same type, fails
  otherwise)
* Give a resource to the ground (plant the resource)

* Attack a building
* Attack another globule (even on your own team)
* Attack a resource (destroy it)
* Attack the ground (drop a resource)

* Push a building (several pushes move a building)
* Push another globule (push it to one side and move into its place if
  possible, else fail)
* Push a resource (move it)
* Push the ground (go to it)

Planting a resource will cause it to disappear if it's incompatible
with the ground-type (e.g. if you plant algae on the ground or stone
in the sea), or sit there and perhaps grow otherwise.  Planted
resources that can grow (wood, wheat, algae) will start off at 1/5.

One of the big problems with the game right now is that globules tend
to get caught up in rat-runs.  Allowing them to push each other out of
the way, or move buildings to ease congestion, would reduce that
problem.  Note: two globules pushing each other in opposite directions
will swap places.

Note: walking into a building wouldn't cause a unit to heal/lunch/etc..  For
example, a unit could simply walk through a friendly building rather
than around it.

__ Building buildings __

Rather than specifying a certain number of globules that can work on a
building, the reward system would have an optimal number of globules - so
you get more reward for going to an under-staffed building and less
for an over-staffed one.

Rewards for adding to a building would be based on:

* How complete the building is (so globules are encouraged to finish one
  building before starting the next)
* How long it's been since the building last got added to (so globules
  are encouraged not to let building sites languish)
* How many workers are already working on it, compared to the optimum
  number
* Whether they are losing hit points faster than gaining.
  (So buildings under attack get worked on faster)

__ Attacking buildings __

The health of a building is measured when you start attacking it, and
again when you stop.  The reward for damage done is proportional to
(starting damage - ending damage)/(time taken).  This way, units are
encouraged to gang up on buildings (more damage in less time), and not
to waste time pounding away at hives that self-heal.

__ Stocking up buildings __

Inns, hives, and towers need maintenance.  Again, they have an
optimum number of helpers, and calculate their rewards based on:

* How many (*not* a percentage of) resources they have
* Whether they have more or less resources than a little while ago

__ Reproduction __

Whenever a hungry globule goes into an inn, its genes are harvested by
the inn.  Globules can't deposit genes unless they're hungry.  The inn
stores the last N genes it harvested, where N is the number of
globules that can be in there at one time.

Whenever a hive wants to create a new globule, each inn selects a new
"candidate" from the available genes, with a probability based on the
fitness score the globule had when it went into the inn.  The glob's
fitness score is then reset to 0.  The hive looks at all of the inns
owned by the player, and selects one (or more) genes with a probability
based on how *different* the genes are from other candidates, ignoring
the score of the depositing globule.  This encourages diversity, even at
the cost of efficiency - which should make for a more interesting game.

Hives will usually take more than one set of genes and recombine them
to form a new set of genes.  I might try getting inns to carry out
this step, and perhaps to allow globules to deliberately mate with one
another inside the inn.

If no candidates are available (or if less than a specified percentage of
globules have visited an inn during the game), candidates are generated
from the general population.  I'll need to do some trickery here so
that very early generations work OK (where everyone dies of hunger
right away), without ruining it for actual, useful games.

__ Defection __

To discourage globules from defecting to different sides whenever they
like, there'd have to be a large penalty for defecting, but an equally
large benefit for eating fruit.  That way, globules are unlikely to
defect unless they're offered lots of fruit (somewhat like the current
system, but fairer IMHO), or if something really bad happens to them
(like they get cornered by lots of enemies).  Defection would have
some very interesting effects in terms of genetics, as you're adding
very different genes to your pool.

__ Capabilities __

Currently, units can either gather, fight, or fly (I've read that
flyers can fight in recent versions of the program, but haven't seen
it in practice).  There's talk about changing this to a more malleable
system.  I've got two ideas about how this might work - I don't have a
preference, so please let me know.

A: much like now, there are three types of unit: those that can
give/take, those that can attack, and those that can take off/land.
Which capability you have is determined by the hive.  If we now have
flyers that fight, how about adding flyers that give/take?

B: Each unit has (say) 9 points to share between harvesting, attacking
and flying.  So a 3/3/3 globule can harvest slowly and inefficiently, can
attack weakly, and can fly for a few spaces.  A 0/0/9 globule can fly
indefinitely, but can't attack or harvest.

The first solution is easier and more in-keeping with current
practice.  The second seems more interesting, but might need more globule
graphics to be created, and I'm not sure how scores would be evolved
and affected by the player.  If you could have unit building work any
way you like, how would it work?

One possibility is to keep the system of unit types and allow players to
create as many types of unit as they like - but defining a unit type
means defining the degree of reward and punishment they get for certain
actions.  For example, a classic "worker" would get lots of reward for
harvesting, but none for fighting.  Over the generations, workers would
evolve to be excellent harvesters but have no fighting ability.  It
would be interesting to see whether they try to hang on to any flight
ability, to get themselves out of trouble here and there.

__ Incentives __

I would like some system of global incentives - so if you want, you
can bump the "aggression" value up, rewarding your warriors more for
random acts of violence, and watch them go on the rampage.  Then
later, put it back down again so they have a chance to recover and
train.


__ Conclusion __

That's my lot for now.  If this sounds like the basis of a good plan
to you, I'll post it up on the forum to get some wider input.  As I
say, this is a weekend project for me, and an ambitious one at that,
so there's a decent chance nothing will come of it.  But I hope I can
help.

My big questions are:
does this seem like a good idea in principle?
What other new features could I crowbar in?
What features should I take out?
Do any of you have GA experience you can share with me?
What else needs to be rewarded/punished in the fitness function?
Ignoring practicalities for a moment, how would you like an ideal race
system to work?

        - Andrew




reply via email to

[Prev in Thread] Current Thread [Next in Thread]