Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ MUSHclient ➜ Lua ➜ Mapping - Pathing
Mapping - Pathing

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1  2  3  4 5  

Posted by Nobody   (38 posts)  Bio
Date Reply #45 on Fri 22 Dec 2006 06:45 AM (UTC)
Message
Sorry for the thread resurrection but I was working on my own mapper when I stumbled across this thread. I love the algorithm presented earlier (the gas particle thing) which is both efficient and elegant.

Being a perl guy rather than lua, I converted everything to perl and ran the same code/benchmarks that you did. While the results are practically the same, there are a few that are different, which means either I screwed up (most likely) or there's some really subtle trick that I'm missing.

The 'check all paths' versio n(the first one without optimisations) gave me the following output:

Rooms = 257
Made 8,168,729 particles to do that
Time taken = 498 secs

As you can see, this is slightly different from the lua version, which gave 8,178,551 particles in 275 seconds. While the time is considerably slower (roughly half as fast) I'm more concerned with why my version didn't build quite so many particles (10,000 or so less). This leads me to believe that something in my version is broken and is not finding all paths (I've had a few choices result in 'no path' for some reason, even though I think all rooms are accessible from each other. One area that was giving me problems is the 'plain hallway' rooms, when I was debugging one time it got caught in a loop somewhere around there. Trying to narrow down exactly where was practically impossible because of so many iterations and data to examine.

So, I'm wondering if there's a way to get more detailed output on both the lua version and my perl version to see what the difference is, and then hopefully I'll be able to figure out what mine isn't doing that it should be. Perhaps you could make it print out each path it discovers into a file, and then email that file to me? Then I can do a simple comparison to figure out which path is failing and then I can focus on that.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #46 on Sat 23 Dec 2006 07:42 PM (UTC)

Amended on Sat 23 Dec 2006 07:48 PM (UTC) by Nick Gammon

Message
I re-ran the test to make sure. The results I get this time are:


rooms =  257
Made 8176447 particles to do that
Time taken =  205 seconds


This is different from both my previous results, and your results.

Quote:

This leads me to believe that something in my version is broken and is not finding all paths (I've had a few choices result in 'no path' for some reason, even though I think all rooms are accessible from each other. One area that was giving me problems is the 'plain hallway' rooms, when I was debugging one time it got caught in a loop somewhere around there.


Well it is possible my version isn't perfect, however your comment about getting in a loop is a worry, as really the algorithm should check if it has been in a room before, and if so, drop the particle. Thus I can't really see how it can loop.

A possible problem is that we are not using identical room data, so the sensible thing is for me to email you my room definition file (in itself 23 Kb before zipping it).

It shouldn't take much effort to convert that in a Perl-compatible table, even if you write a small Lua program to do it. Then you can be sure we are using the same raw data.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #47 on Sat 23 Dec 2006 07:53 PM (UTC)
Message
I have sent the room data to your forum email address.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nobody   (38 posts)  Bio
Date Reply #48 on Sun 24 Dec 2006 05:56 AM (UTC)
Message
Thanks Nick,

I got the file, and re-ran it and got the following output:

Rooms = 257
Made 8168729 particles to do that
Time taken = 507 secs

This is identical to my first reading (except for the time taken, this one took 30 seconds longer - the probable reason is because I had another process chewing up the other half of my CPU so it might have not swapped as efficiently as it should have).

I changed my code to add one extra line. After storing the data returned from find_path, it then prints it out, so I have a log of paths:

Path from room 21096 to room 21308: w,w,s,s,s,s,s,s,e,e,s,s,s,s,u,n
Path from room 21096 to room 21037: e,e,e,s,s,s,s,s,s,e,e

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.

In the interests of my mudmapper, I converted the pathfinder script into one that retrieves the rooms from an Access db. In perl I use the Win32::ODBC module to access it and run queries. I gather the lua version is somewhat similar. I expected it to be slow, but not quite this slow.

Rooms = 257
Made 8956621 particles to do that
Time taken = 16996 secs

Yes, you read it right - 4 hours 43 minutes 16 seconds.


I figured that a map of a large number of rooms from a mud will be better stored in a db rather than a (hash) table. There are a few reasons why, which I wont get into. Hash tables of course are faster, and don't require as much disk access. However I think the expandability and other benefits from a relational db make this the preferred choice. The speed isn't that important if your mapper is going to be just tracking your location and/or searching for specific paths. If you intend to use it for listing *all* paths (as the benchmark code above did) then perhaps a hash is the way to go.

I'm toying with the idea of a hybrid. One that loads all data from a db to a hash on startup, and when adding a new room, adds it to both at the same time (thereby removing any problems with having to 'save' it constantly from the hash table to the database). I haven't thoroughly explored it yet, I'm still toying with ideas.

My next step is to use that optimised version above on the db version and see how much faster it is. Another thing I'd like to try is running a single path search on a db (both Access and hash table version) with a lot of rooms: 20,000+ would be a good start, my ideal would be 50,000+ or 100,000+ rooms to find out just how long it takes on a 'real' map.
Top
Posted by Shadowfyr   USA  (1,791 posts)  Bio
Date Reply #49 on Sun 24 Dec 2006 09:41 PM (UTC)
Message
You're kidding right? That long? I think maybe we need to find out what algorythm the Tradewars Helper application used and figure out some way to adapt that. Seriously, one function it had was, "Use probes to find information about as many sectors as possible." This often took only 10-20 probes, to produce a complete map of 10,000 rooms and their contents. Mind you, the
"ship computer" had a map of how the rooms connected, so what it would actually do is:

1. Log into the computer.
2. List "every" sector (room) in the game, which provided the number ID, basic description and exits.
3. Do a "longest path" search for the first probe.
4. Send the probe to the end room and marking each returned room as it want.
4. Do a longest path search for the next probe, which automatically excluded all rooms seen already (it allowed cross overs, but not ones that ended in the same room that the last one did.
5. Send the probe, etc.
6. Repeat 4, until you have all rooms or you run out of probes.

Obviously a "longest path" search **must** be exhaustive. I.e., for it to find the longest path, it must check every "available" path to every un-identified sector, then send the probe to the one farthest away. Mind you, in that case the longest path was usually between 10-20 rooms. However, while it took (on a 386 processor) 20-30 minutes to read the computer data to "build" the database, the searches took all of about 30 seconds each. Now, we are talking about maybe double the rooms, with theoretically, lets just say, twice the path lengths, on a machine that is 1,000+ times *faster* than the Tradewars Helper ran on, and its taking nearly -5- hours to do what is basically a, "find all paths to see which is the longest one from X to Y"?!? Something is seriously wrong with that imho. But maybe I just don't understand how much greater the search time is for longer paths...
Top
Posted by Nobody   (38 posts)  Bio
Date Reply #50 on Mon 25 Dec 2006 04:43 AM (UTC)
Message
Just for further benchmarking information, I ran the optimised version (posted back on page 1 I believe) that runs in lua in about 2-3 seconds. In perl, using perl hashes, it takes 25 seconds. In perl, accessing everything through the Win32::ODBC and running an sql query to obtain room/exit data, took 137 seconds.

So a rough conclusion to be drawn is that perl is between 2 and 10 times slower than lua when using perl hashes. When comparing perl hashes to perl ODBC, it's between 5 and 30 times slower. I'd really like to find the bottleneck and see if it could be eliminated, but I suspect it's just that perl isn't fast at anything except regexps. Still, I think for a mapper it's reasonably fast, as long as you're not going to need to generate hundreds of paths a second you should be ok.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #51 on Tue 26 Dec 2006 02:06 AM (UTC)
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
Top
Posted by Nobody   (38 posts)  Bio
Date Reply #52 on Wed 27 Dec 2006 11:46 AM (UTC)
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.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #53 on Wed 27 Dec 2006 07:05 PM (UTC)
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
Top
Posted by Nobody   (38 posts)  Bio
Date Reply #54 on Thu 28 Dec 2006 12:29 AM (UTC)
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'.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #55 on Fri 29 Dec 2006 02:57 AM (UTC)
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
Top
Posted by Nobody   (38 posts)  Bio
Date Reply #56 on Fri 29 Dec 2006 05:40 AM (UTC)
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.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #57 on Fri 29 Dec 2006 06:13 AM (UTC)
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
Top
Posted by Shadowfyr   USA  (1,791 posts)  Bio
Date Reply #58 on Fri 29 Dec 2006 09:58 PM (UTC)
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.
Top
Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #59 on Sun 31 Dec 2006 03:22 AM (UTC)
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
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.

177,914 views.

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

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

Home