# [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
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.

>   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.

>   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
http://www.kanga.nu/lists/listinfo/mud-dev

```