[MUD-Dev] Tech: Pathfinding with Rooms

[Sanxion]

On Friday, November 30,2001,  David Bennet wrote:

> The co-ordinates are calculated using the exit directions, every
> exit has a direction associated with them and an offset from the
> current rooms co-ordinates.

Interesting, I thought of something similar, but I also see some
problems with a system like this. Do any of your rooms end up having
the same X and Y pseudo co-ordinates?  For instance if you were to
plot your entire MUD world on graph paper, would rooms collide? 
Also, do your rooms ever loop around? (I.E. 5 north takes you back
to your starting point.) Are you creating pseudo co-ordinates at
runtime or these also stored in the database? I guess you are using
pseudo co-ordinates for areas and not the entire world?

> We then 'cluster' the rooms together into blobs and do route
> finding on the clustered blobs.

Nice. How large are the clusters and are all the same sizes? I see
some difficulties that must be overcome with clusters but I can't
formulate them well. I guess clusters are not based on pseudo
co-ordinates or you may end up with rooms that do not connect within
a cluster...

> Then find routes through the blobs themselves, caching the
> results.

Are you caching these in RAM and do you have any precomputed routes
stored in the Database?

> We don't load all the rooms either, all the room data is stored in
> a database which we use for the route finding.

Cool, just out of curiosity what database are you using? I'm
planning on using MySql or Postgres. (because of price)

Sorry for the bombardment of questions, but I find your
implementation witty and bold. I've already coded a A* algorithm, so
a pseudo co-ordinate system would be neat.

Emanuel

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev