Pathfinding in a MUD

You could start by using a variable for a unique id. It is much easier to organize.

I hope this makes sense, Im in a bit of a rush atm,

Heres how I would approach this if I were you.
First assign every room a unique number. There doesnt need to be any relationship between the numbers, but it does help later calculations you may use them for if you dont leave out numbers and just number through a range, say 0-199999 instead of 1-5, 10-20, 45-200000.
Now you have a unique handle for every room, so you should be able to set it up to do a quick lookup of the room''s number. and those neighboring it.
Now you need to decide if you want to search for the first path to your destination or the shortest path (or lowest cost path if youve got movement difficulties) or if youd like some intelligent combination to try to speed things along(A*)


Now, If you want the guaranteed shortest path, use a BreadthFirst Search,its fun to implement, i promise :-), if you want the guaranteed shortest based on a value assigned to each movement, youre going to want to implment Djistraka''s weighted, directional graph searching stuff. If you dont know it, look it up on google. Or amit''s page might have something abt it. If you just want to go with the first path you find, use a DepthFirst Search.

Of those, herusitic searching like A* is the hardest to implement.

Something else that may help you is to develop a system in which you can store information about which rooms your NPC has visited. an array of around 7000 32bit unsigned ints should cover 200,000 rooms as I recall. If you dont know how to do that, ask or look it up, im sure you can find the info on it.

I probably wont be able to go into any further detail on this for a week since Im not actually at my own computer - this is just a friends that im on for a very short pd of time. So, best of luck with your pathfinding system. Always nice to see ppl working on muds still.

quote:

---

Original post by LineFeed
However each room name is NOT unique, and this is the reason why I cannot develop a method of pathfinding.

---

Instead of the name, use the location, which according to that map, is unique. Each room appears to have a unique combination of x and y values.

quote:

---

Due to the way the world is setup there is a slight problem with infinite spaces.

---

I''m not sure what you mean by this though.

The algorithm I''d use for exploration would probably be some sort of bounded depth-first search. You take all the first exits in the rooms you encounter up to a maximum depth (10 rooms, perhaps), then back up one room and try the 2nd exit, etc. This can probably be easily done with recursion or a stack. The only real complication is making sure you can back up at each stage.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

This sounds like you''re playing NannyMUD, where a normal pathfinder will have trouble, since the rooms are not laid out in a logical fashion. That is, if you walk w, s, e, n you might not end up in the initial position again. The only way i can come up with for something like this is storing unique identifiers for every "new" room you encounter, and in each room, have the known path from that room to the target room stored. This could potentially require lots of memory, and since you would probably have doubles stored in the room-identifier list you''d have to do some manual refining of it.
Then again, if you manually train the bot first, showing it the best paths from point A to B, it would be a no-brainer ofcourse, since you''d only have to store the steps you took when training it.
Oh, and let me remind you of the fact that bots are FORBIDDEN on NannyMUD, aswell as on most muds. If you''re caught you''ll probably loose all characters you have on that mud that they can find.


--
MFC is sorta like the swedish police... It''''s full of crap, and nothing can communicate with anything else.

As tok_junior said, some MUDs (text based) don''t adhere to a grid system since in a text based world a "room" could be a closet or a large field. A lot of DIKU/MERC derived MUDs work this way and it can be a godsend when you can cut accross the plains in 10 moves instead of walking straigh through a city or it can stink as in your situation when it becomes hard to figure out your bearings in the overall world. A while back I wrote something for a MERC derived MUD I was working on that made little ascii maps of single areas at a time but it was some messy recursion that required all of the rooms to actually be connected which isn''t always the case and of course the "infinite space" you talk about kind of made the maps look different depending on where you started the mapping procedure. I also had access to the code and area files so I don''t know if that is an option for you. If not, there are MUD clients available like ZMUD that have a zelda-esque mapping thing available although I think that ZMUD now costs a small fee to register.



Evillive2
E-Mail

Thanks for the ideas. I was thinking of using an identifier number. I was going to append it onto the room name...

By infinite spaces I mean go east, then west won''t always land you back in the room you came from, but these situations are not often, and are very well documented.

Any further ideas would be appreciated.

Well, you need to find something (anything) that is unqiue about a room. If the room''s name isn''t enough, then the room name + exits is probably not enough either. If the MUD doesn''t supply you with an internal unique room number or coordinates, then it''s becoming rather difficult. You can of course also use the room description but even that must not be unique (several rooms "A muddy field" with identical descriptions). Using descriptions also adds a lot of other problems, because you might have to filter out weather messages (the room didn''t change just because it started raining), items and players there or time of day (for example "It''s too dark to see anything" at night).
While you can probably come up with something, you need to ask yourself if it wouldn''t be easier to find a more mapping friendly MUD. And if you find one, please tell me about it.

I had one idea but I am not sure how to implement it. Because of the nature of the mud it would be possible for me to aquire several items and carry them on my character and leave them behind for maping purposes. Then picking them up come back to look at the connections as I go along. The way a look command works easily seperates items and weather events from room descriptions, names and exits. When your moving from room to room you get Room Name (exits), but when you look you get a more seperated list starting with Room Descriptions, Weather Events, Exits, Player Characters, NPC, and items. Always in an order like this. If it matters its an LPMUD running the TMI-2 1.1.1 mudlib on MudOS v22pre8

watch the movie caled "the cube"

quote:

---

Original post by LineFeed
I had one idea but I am not sure how to implement it. Because of the nature of the mud it would be possible for me to aquire several items and carry them on my character and leave them behind for maping purposes. Then picking them up come back to look at the connections as I go along. The way a look command works easily seperates items and weather events from room descriptions, names and exits. When your moving from room to room you get Room Name (exits), but when you look you get a more seperated list starting with Room Descriptions, Weather Events, Exits, Player Characters, NPC, and items. Always in an order like this. If it matters its an LPMUD running the TMI-2 1.1.1 mudlib on MudOS v22pre8

---

This is the common way of mapping out for example a maze. In the first room, drop 1 coin, in the second room, 2 coins, and so on. However, problems arise once people start picking up your stuff, or dropping their own
This bot, will it run with wiz-priviliges or as a normal player? If it''s got wiz-priv, just use the current room-name, which is unique. This isn''t accessible for a normal player though, so if that''s the case, manual learning and then crossbreeding those paths are the only way to go i guess.

I will be running the bot as a player. If I was a wizard I would have access to the room numbers, but my status as a player won't allow me to develop a unique identifier for the rooms. I can however aquire a bunch of useless items that no one would be interested in picking up. This might sound stupid, but I am not sure how I should go about the situation even if I could drop a unique item in each room as I go. I am having a slight problem developing the structures I want to use to store the node information and the node relationships. I would perfer to segment the maps into levels, but if I had to I could define room by room where these levels begin and end. I am worried about memory usage for maps containing several hundred rooms.

[edited by - LineFeed on March 20, 2004 4:18:07 AM]

In some muds, certain guilds has ways to see whose realm they''re in.
Plus, don''t ever think noone would be interested in the stuff you drop, especially if they''re unique or rare items. When i play, i usually pick up EVERYTHING. And a newbie usually picks up everything, no matter if he''s seen it or not.

By unique, I meant I could have a separate item for each room. And with this mud its not unusual to see rooms littered with items that even newbies don''t want. The mud purges items slowly so anything I drop will be around for awhile. I figure the items won''t be around long enough anyway. I just need to leave the items long enough for my map to be created. I should only have to create this map once. The game doesn''t change much. I just wanted to save myself the trouble of creating a huge map by hand. However it is possible to hard code some of the map, or at least code the rooms which would confuse the mapper, but how would I integrate the hand made portions with the auto generated portions?

Well, that shouldn''t be too hard. Make a function (AddExit() for example) that takes the room you want to add, together with a list of the different exits from the room and where they lead to. Ofcourse this won''t work in some cases, since one exit could be "exit" and the connection in the other direction could be for example "enter house". That could all be handled with more manual editing though. You could for example, in the list store the exits different names for the different directions.

I watched the cube. It didn't help at all, and it was a weird movie. But it was cool. Anyway I think I found a way around all of the problems. Check this out and let me hear your opinions.

I am going to blindly add every new room without checking to see if it is the array. By new room I mean every room connection that is 0. (I use 0 to mark a connection as unexplored.) This should allow me to store the identical rooms in the array with seperate connection information. I will then check the rooms when I am expecting a certain room.

Example

Only assumption is that room A is unique. (This is easy to satisfy)

We start in A.

Collect the room information and add it blindly to the list because we are expecting a new room. Check the exit structure for the first exit with a 0 for the room number. Go to that room. Add it to the array without checking if it is in the array, because we have multiple rooms with the same names. Then go back to the room we were just in, this time checking the array to see if it is the room we are looking for. If it appears to be we will just assume that it is. Then, continue on with the next 0 connection in the room. However if it isn't the room we were looking for, then we'll wander around checking every room until room A is found again, then proceed with the next 0 connection.

Sorry about the large post. Please reply with your comments/sugguestions.


[edited by - LineFeed on April 5, 2004 4:44:26 AM]