[MUD-Dev] Simulated Populations

phlUID phluid at mindless.com
Thu Jan 20 23:11:51 New Zealand Daylight Time 2000

Vladimir Prelovac wrote:
>   I am just having a look at this from the programming side of view. If
> you are going to have large numbers of mobs moving from one location to
> the other (ie. hunting, searching for food, going to war...) you will have
> to spend a *lot* of CPU time calculating shortest paths. And I still dont
> know an efficient way to handle this. Maybe there is a way to build this
> database with some kind of implemented solution to this problem within it.

Well, there are a couple of thoughts on this:

1. We could just throw out the whole path finding thing and make mobs
   wander aimlessly. This would make sense because populations would
   remain mostly concentrated in one locale. Obviously, this isn't the
   fun way. :)

2. The database could calculate inter-wilderness paths upon bootup.
   I've never heard of this being done before so I'll give a quick
   description. Say I have a dwarven population in the north part of
   the map, and I want to make routes to all the other populations
   they might want to later interact with. I can use variations of
   the A* pathfinding algorithm with different heuristics to generate
   different paths through the wilderness. When one of the dwarves
   enter's a room that is part of this path, they just have to pick
   up the path ID and fallow all the path pointer's along the way to
   it's destination. This creates invisible roads through which the
   dwarves will move. Ranger's can also use tracking with zero CPU
   time. The only problem with this is that the paths will break if
   one of the rooms on them is destroyed. In this case, we will have
   some method of destroying the path, or else all the dwarves will
   end up in some deadend all trying to go east. :)

3. I use a wilderness system to connect different areas. This system
   shows a small overhead map in your room description depending on
   your current position within the wilderness. Luckily, the wilderness
   is graphed, so path finding is extremely fast when determining the
   way from one coordinate to the other coordinate. Of course, this
   doesn't account for the fact that the area's that are not part of
   the wilderness don't have coordinates. I will need to do cpu
   tests on a hybrid version of this system, using both graph path
   finding and non-graph path finding.

4. I can use regular pathfinding, but instead of just sitting there
   and sucking up the CPU to death, I can use the idle time spent in
   select() utilizing the path finding algorithm. Dwarves don't
   need paths to suddenly appear at that very pulse because they can
   effectively wait a few minutes for an answer. This conserves CPU
   and produces very reliable results. What's the point of wasting
   CPU cycles when you can use them to make the game more alive?

I believe that it is also possible to combine any number of these
elements together into one system. For example, I could use graph
pathfinding and wandering, so that a dwarf would wander around it's
area until it stumbled into the wilderness and then have it determine
if it wants to go back or go to another area. Another possibility is
to use pregenerated paths with wandering, so dwarfs will wander aimlessly
until they stumble upon a room with a path. It can then decide if it wants
to fallow that path.

Vladimir Prelovac wrote:
>   Second matter is problem of handling system crashes or at least reboots.
> You would obviously need a very safe and precise method of saving all the
> data that have evolved (population info, every mob's current goal, etc
> etc) and restoring them back, because you dont want your world to start
> building itself from scratch every time you reboot.

   Luckily, because Spellbound uses C++ every object in the game inherits
  from a 'Savable' class. Because of this, Spellbound is 100% persistent.
  When the game saves to disk and loads from disk, it is in the exact same
  stage as it was when it went down or crashed. Total database saves are
  done periodically ever hour, so the worst that can happen is a time
  warp. The database is only copied if the save is successful.

Vladimir Prelovac wrote:
>   The whole idea is of course very interesting. But also the effort that
> has to be put into building it is simply HUGE. Hope you will finish it
> though.

   Me too. There never seems enough time for a good coding run. For some
  odd reason people start asking questions about where you have been and
  where all the twinkies and soda keep going. :)

Amos Wetherbee,
The Spellbound Project

MUD-Dev maillist  -  MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list