[Home] [Downloads] [Search] [Help/forum]

Gammon Software Solutions forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  MUSHclient
. -> [Folder]  Lua
. . -> [Subject]  Mapping - Pathing
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?
(New message)
Subject: Mapping - Pathing
Name:
Your forum user name.
Register forum user name
Password:
Your forum password.
Forgotten password?
Message:
Message to be posted (in English, please).
Forum codes:
Check this if your message uses 'forum codes' or templates (auto-detected for new posts).
Forum codes Templates

Save this message ...

Subject review (reverse sequence)

Pages: 1 2  3  4  5  

Posted by Onoitsu2   USA  (246 posts)  [Biography] bio
Date Wed 11 Apr 2007 11:09 AM (UTC)  [ quote  ]
Message
Since this WAS a very hot discussion, and is still more likely than not an idea in a lot of user's heads, I have tried to track down some things on it, and have located an Open Source Client, that HAS a MAPPER, so that such code can be examined, and perhaps a mapper can be built by the "Programming Community" since the release of mushclient's source.

http://www.mudmagic.com/mud-client/source_download.php

That is the URL to DL the source in a variety of archive types. The Windows Zip is 3769KB (roughly 3, nearly 4 MB)

I am unsure as to the Language used, as I have not DL'd the source as I am having connection difficulties (Dialup only wanting to connect at 26.6 for some odd reason)

Laterzzz,
Onoitsu2
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Sun 07 Jan 2007 08:19 AM (UTC)  [ quote  ]
Message
Well, there is a data structure called the multimap, which can store several values with the same key. That way you could keep very quick lookup, and when you have conflicts, you would resolve them however you would normally resolve them. (You have to resolve them somehow anyhow.)

One main difference with this data structure is that you wouldn't specify just a key to remove, but a key-value pair so that it leaves other values that might share the same key.

An easy but not optimal way of implementing this is to have every key point to a list of values for that key. (This is not optimal because most of the time the list overhead is useless. It might be better to only have a list if you actually need one, but that adds extra complexity.)
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Nobody   (38 posts)  [Biography] bio
Date Sun 07 Jan 2007 06:32 AM (UTC)  [ quote  ]
Message
Who wants to help me plan out some data structures for a mapping system that does everything above, but also has the ability to learn new rooms and add them (with appropriate linkage to other rooms) ?

It doesn't really matter much about which language is used - perl hashes are pretty much the same as lua tables in this case. The trouble I'm having is searching for a room by title. I was hoping to have a way to search for something quickly (I was thinking of somehow using a room title as a key, but that falls apart when multiple rooms with the same title occur) so I guess I'll have to do the old brute search method.

What I'm aiming for here is a mapper that can monitor your position and keep itself updated about which room you're in, and one that adds the room if it's not found. I'm not too concerned right now with things such as detecting rooms and making it all 'portable' for all muds. Right now I'm just focusing on the data structures for storing the data. Who has some ideas?

I'll be storing the following data: Room title, description, vnum (not given by the mud, generated by me), exits. Room title and description will be strings, vnum obviously will be int, and exits will be a hash (or table) of direction->vnum.

So far I have a hash with the vnum as key, and the text data as a sub-hash (with the exits data as a sub-sub-hash). Can anyone think of a better way ?
[Go to top] top
Posted by Shadowfyr   USA  (1,774 posts)  [Biography] bio
Date Tue 02 Jan 2007 07:28 PM (UTC)  [ quote  ]
Message
Mind you. Its probably a good idea to make it so that if "no" path is found with those limits, that it looks for one with a bigger limit, so you start with 30, then if not found, try 40, etc. Or, maybe even let the player specify, something like, "find orc shaman : far". Where that designates that it should use a bigger limit, or just ignore them. Its not impossible for some mud to have a path from the farthest corners to each other be 30+ rooms. Of course, if using this with a GUI, you could simply have a set of buttons to define if you want "near", "close", "distant", "far" or "unknown", as a search limit. And if previous successful searches where stored, so going from the bank to Zorg's Merchantile was already found, the "current" distance would be stored for those start/end locations, so that a new search only looks for something "shorter than or equal to" that.

In other words:

Near - 10
Close - 20
Distant - 30
Far - 40
Unknown - infinite

So, if the path from the Bank to Zorg's is "known" to have been 19 last time, it won't look for any path longer than "Close" the next time. The only issue is how many prior searches it stores, so you might want an option of "save this search", or even just throw out ones that haven't been used more than once after 10 active days. That way you don't have to look through 50,000 * 50,000 prior searches (in the worst case, like some moron going to every room, one at a time, and searching every other room in the game world...), just the "often used" and most recent ones.
main {
__if (Schrodinger_Cat is Alive or version >= "XP"){
____if version = "Vista" then Performance /= Number_of_Cores;
____call Functional_Code();}
__else
____call Crash_Windows();}
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Tue 02 Jan 2007 06:49 AM (UTC)  [ quote  ]
Message
Exactly. An exhaustive search is probably the safest, and with a limiter, should not consume your CPU for 10 minutes.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Shadowfyr   USA  (1,774 posts)  [Biography] bio
Date Mon 01 Jan 2007 01:30 AM (UTC)  [ quote  ]
Message
Of course. My point is that an optimization that didn't "know" that the underground existed at all initially might look for the path to the area boundary instead, this being flawed, since once the underground is known, its no longer the most reasonable path.
main {
__if (Schrodinger_Cat is Alive or version >= "XP"){
____if version = "Vista" then Performance /= Number_of_Cores;
____call Functional_Code();}
__else
____call Crash_Windows();}
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Sun 31 Dec 2006 03:22 AM (UTC)  [ quote  ]
Message
A simple limiter (eg. stop when path is 100 long) would at least stop lengthy CPU loops.

Then it could be up to the player to "manually" move closer to the destination. Assuming you have some idea of the topology of your world, you could generate a path to the exit from the city that you think leads to where you want to go, and take it from there.

Quote:

The unique thing about it being that *every* part of the city of Qeynos is accessible through that underground, just by moving 2-3 rooms.


The existing pather will discover those, because it does an exhaustive search. Assuming those rooms are known, it will take the shortest path, which in this case would be underground.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Shadowfyr   USA  (1,774 posts)  [Biography] bio
Date Fri 29 Dec 2006 09:58 PM (UTC)  [ quote  ]
Message
Yeah, you can hope that you can pick such a path. Just to illistrate the problem with that hope though, I have been playing EQ2. Yeah, I know, its a graphical system, but there are clear areas and clear checkpoints along the way, like buildings, roads, etc. There is also an "underground" I stumbled across. The unique thing about it being that *every* part of the city of Qeynos is accessible through that underground, just by moving 2-3 rooms. Now, the "room" you want to get to, like the South Qeynos pet shop might be 20 rooms away, but if you are in the Willow Woods, for example, it might be, parsing the distance into text terms, 10 rooms to get to the underground, 3 rooms in there, then 20 to get to the shop, while the "alternate" route, that takes city zones into account, would take 15 to get to the boundary to High Castle View, 15 to get to North Qeynos, 30 to get through there, then another 30 to get to to shop.

The mapper needs to be smart enough, in other words, if you are going to do it that way, of "knowing" that a short path does exist and that it makes sense to go to the next city zone, instead of the underground, or like in EQ 1, running all the way from Qeynos to Freeport, instead of going the opposite direction to the Plane of Knowledge teleport book, then through there to the POK stone that links out to Freeport. A distance of 3-4 areas, each (again, projecting it into a text world) 30-40 rooms across, vs. going straight from outside the city walls of Qeynos to just outside West Freeport.

Mind you, one option, and one that makes sense imho, is to have something like quickpaths to "named" locations. A player could set specific places, as "always follow this path". That could include known crossroads. That way the "optimal" path know at that point could be stored (and rechecked later at the players option). Then, when you need to look for some place you could optimize things a bit by taking the "known" part of a path, then using its end point as the "start" when looking for a destination. Though, again, that means having some awareness of "Where" that endpoint is. Hmm... I suppose, one things you could do is use a base point, like initial login for most people, and store the data for rooms in a tree of sorts, so that the search can generate a rough estimate of distance from a known point that an end point is, then *guess* if its a good candidate to search off of. It kind of depends on how smart you a) want to make it and b) need to make it to work well.
main {
__if (Schrodinger_Cat is Alive or version >= "XP"){
____if version = "Vista" then Performance /= Number_of_Cores;
____call Functional_Code();}
__else
____call Crash_Windows();}
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Fri 29 Dec 2006 06:13 AM (UTC)  [ quote  ]
Message
Well, I was thinking if you are in South City, and you want to go North City, and you are somewhere in the bowels of South City, then you choose a road you know leads you to North City (eg. Northern Highway) and ask for a route to that.

Even if your initial paths are south, you hopefully get the optimal route that takes you to the edge of the city. Then, following the main road north, you reach the gates of North City. From there you request a path to your final destination.

As for test data, you could just randomly generate heaps of rooms.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Nobody   (38 posts)  [Biography] bio
Date Fri 29 Dec 2006 05:40 AM (UTC)  [ quote  ]
Message
While that seems to work, I can think of a simple situation (and one that's likely to exist in alot of places on many muds) right off the top of my head that would screw it up.

Say, for example, you're at the north gate of a city, and you know you have to go north to get to your target. So (with some modifications) you can make the mapper ignore any exits that arent north. Sounds fine and dandy, but what about this: Somewhere north of this exit, there's a path that branches off to the east, and links up with the path that is sent out from the east gate of the city you're in. Now you're searching that entire east branch as well. And if there's one linking that east path to a south path, then again you're locked into exploring all those unnecessary paths.

The upside of course, is that maybe there's a secret hidden path that's actually quicker that you might not know about. Perhaps one featuring a portal or something.

I dunno, I still think with 50,000+ rooms the speed would be enough that it wouldn't be a hassle. Guess it's hard to test something like that though since there's not much chance of getting a workable test system with that many rooms on it.
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Fri 29 Dec 2006 02:57 AM (UTC)  [ quote  ]
Message
I think that to make large maps efficient you probably need to zone them somehow. For example, if you know the room you want is somewhere to the east, then checking each road that leads west is probably a waste of time.

Or, you might simply limit the pather, so that after it becomes (say) 30 rooms long it simply stops.

Thus, if I wanted to go from some city to some other city a long way away, I might first find the exit from this city - and go there. Then I find the next city. Then I go to the room.

Breaking down the problem like that could make the mapper useable, and be more practical anyway.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Nobody   (38 posts)  [Biography] bio
Date Thu 28 Dec 2006 12:29 AM (UTC)  [ quote  ]
Message
Yeah I've used that so far, I just wanted something with alot more rooms to see if the finder chokes on extremely large paths when searching 30,000+ rooms. By 'chokes' I mean 'becomes too slow to be useful'.
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Wed 27 Dec 2006 07:05 PM (UTC)  [ quote  ]
Message
This confirms what I said before, that the particle count depends a bit on the order on which rooms are visited.

As for the standard MUD, I just used SmaugFUSS, which is available as a download from this site.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Nobody   (38 posts)  [Biography] bio
Date Wed 27 Dec 2006 11:46 AM (UTC)  [ quote  ]
Message
Thanks Nick,

When I first checked the output, I noticed a few thousand lines of differences, and I groaned at the thought that I had royally screwed up. Then I started analyzing them an realised that the differences, while noticeable, were in fact different ways of getting to the same place - 4e4n instead of 4n4e. When I compared the length of each path, they were identical. So it seems that due to the order the exits are chosen, you can end up with a path the same length, but using less particles. Interesting.

My next step is to add a weighting to certain exits depending on other conditions: eg, damage rooms, exits that are locked, rooms that you have to kill a certain mob to access, and to factor them into the pathing algorithm. It shouldn't be a big deal, but I still think it would be useful. For example, a room that damages you might only be used if the alternate path is some huge length around. Another option is to return an array with the top 5 paths, so that the user can then choose which one they want.

Hmmm there's so much else I want to do, but baby steps, baby steps. Incidentally, is there a standard downloadable mud server that comes with a few ten-thousands of rooms already built in and linked? I might use that for testing the large-path speeds instead of trying to manually link all my own.
[Go to top] top
Posted by Nick Gammon   Australia  (18,769 posts)  [Biography] bio   Forum Administrator
Date Tue 26 Dec 2006 02:06 AM (UTC)  [ quote  ]
Message
Quote:

Obviously all 65792 iterations are in there. If someone could do the same with their lua version, perhaps I can figure out which rooms are giving me different results and then I can focus my debugging and analysis on those specific parts.


As discussed earlier in this thread it is possible to use less particles to discover the same path, I think, depending on the starting point. So it is possible you are generating the correct paths, but in a slightly different order.

Anyway, I am making a file of the generated paths as you requested, which I will zip up and email shortly. If you sort both yours and mine into sequence, and then run a "diff" on them, it should be easy to spot any differences.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

14,619 views.

This is page 1, subject is 5 pages long: 1 2  3  4  5  [Next page]

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Go to topic:           Search the forum

[Go to top] top

[Home]

Written by Nick Gammon - 5K

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( http://www.gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Internet Contents Rating Association (ICRA) - 2K]    [Web site powered by FutureQuest.Net]