Gammon Forum : MUSHclient : Tips and tricks : The Script Project from Hell - autospeedwalker from Any Point A to Any Point B

Entire forum ➜ MUSHclient ➜ Tips and tricks ➜ The Script Project from Hell - autospeedwalker from Any Point A to Any Point B

The Script Project from Hell - autospeedwalker from Any Point A to Any Point B

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

Posted by

Neurowiz (17 posts) Bio

Date

Tue 22 Oct 2002 05:13 PM (UTC)

Message

The MUD: Achaea

The problem: I am a city guard in the city. This city probably consists of 100 to 200 rooms (maybe more). At anytime, I could be at anywhere in the City, and I want to be able to simply type something like /autogoto("The City Gates"), say if there's an emergency and I need to get to a location in a hurry. Kinda hard to do with speedwalking aliases - all the permutations of starting points and ending points.

In my mind, here's the script would do:

1. Determine my current location.
2. Using some sort of map that I've created in memory, probably a 3d array where the 2d is the "map" of rooms and the third (and more)d would be the various exits and room name - compute the shortest distance from where I am to the destination given.
3. Create a speedwalk from current to target location.
4. Run the speedwalk.

Sounds simple, no? I'm thinking it would be a LOT of work. The two largest tasks are:

1. Putting the map into some sort of format that would know the exits for each room and be in some sort of grid so that..

2. I could run an algorithm that finds the shortest distance from point a to point b (think of the old maze walkers that we programmed in CS101 - not just a solution finder but a fast solution finder that finds the shortest/fastest route amongst many.

Anyone ever seen this done on another client that maybe I could convert? I saw the GPS thing in another thread, but I didn't look like what I was looking for, plus the polish threw me off.

Or is there another method that maybe I'm overlooking?

Regards,
Neurowiz

Top

Posted by

Shadowfyr USA (1,788 posts) Bio

Date

Reply #1 on Tue 22 Oct 2002 06:24 PM (UTC)

Message

Hmm. I have been thinking about this sort of thing myself, but figured on using an external COM program to do it. Scripting it would be insanely complex, take far more time and lacks many useful things, including the ability to actually put all your exits and the room name into a single piece of data. This is something I really miss about vbscript. I used to use QBasic for quick and dirt stuff and it had the ability to do:

type Room
ID as integer
Name as string * 20
Exits(10) as integer
end type

Though.. I am not sure I ever tried to use an array in one like that... But you could stick everything into a single place. You could do the same in a full COM, but in scripts you are pretty much stuck with arrays and simple variables. :p This makes things far more complicated. However the good news is that a decent path finder can return a result of a 20 room path in a 10,000 room area in less than a second, even without any of it on a grid. I just wish I had a clue how the program I saw peformed this miracle. lol

Top

Posted by

Neurowiz (17 posts) Bio

Date

Reply #2 on Tue 22 Oct 2002 06:40 PM (UTC)

Message

You can use VBScript v.5 and later to do classes:
http://msdn.microsoft.com/library/en-us/script56/html/vsstmclass.asp

I've been looking at the LeeMorgan(?) method of pathfinding. It seems pretty straight forward.

I would iterate through an array of classes of locations(built from a text file, perhaps?) and find the instance with the destination name. Using the LM algorithm, find the shortest path, using your example of a class def to find connections between locations.

Hmm.. I'm starting to think about this more... my brain hurts!

Top

Posted by

Shadowfyr USA (1,788 posts) Bio

Date

Reply #3 on Tue 22 Oct 2002 07:10 PM (UTC)

Message

Hmm. I have a help file for vbscript 5.5, but don't remember seeing anything in there for classes like that.. But then MS seems to like to scatter little gems like that into obscure corners where you can't find them, rather than puting them where people actually look. lol

Guess I should check out LM's algorithm. I did a quick search and it turns out the program I was talking about used one called Djikstra's Algorithm. However I suspect that there has to be a more efficient one, since this one assumes that different paths have different time costs, etc. Useful for muds where the terrain types effect movement, but not for the more ordinary ones. Though.. Being able to mark rooms with a danger level that is dependant on the size and aggressiveness of a mob could be a good use of that algorithm too... Hmm.

Top

Posted by

Nick Gammon Australia (23,120 posts) Bio Forum Administrator

Date

Reply #4 on Wed 23 Oct 2002 03:29 AM (UTC)

Message

It would make a great plugin!

You might be able to do it with a two-dimensional array. First dimension is room number (or name), the second dimension a bitmap showing if you can go north, south, east, west, etc. from this room.

eg.,

north = 1
south = 2
east = 4
west = 8

If a room led north and east you would store 5 as the bitmap.

Maybe another couple of dimensions to give you the coordinates in the city (eg. 23, 84 begin 23 squares north, 84 squares east).

You would exclude dead-end exits (eg. a north exit, but which only leads to a shop, so it isn't useful for speedwalking).

Once you had that information, you could work out from A to B, depending on their repective coordinates whether you are heading (say), north and east, or south and west. Then keep choosing exits in the general direction you want to go. Make a list of possible candidates, and then choose the shortest one in the list.

Hopefully wouldn't be *too* compute-bound. :)

- Nick Gammon

www.gammon.com.au, www.mushclient.com

Top

Posted by

Nick Gammon Australia (23,120 posts) Bio Forum Administrator

Date

Reply #5 on Wed 23 Oct 2002 03:37 AM (UTC)

Message

A simpler approach, which doesn't involve mapping the entire city, might be to simply make a self-learning system that stores failures rather than successes.

Eg. a simple array, showing for each room which direction is *not* a success to walk.

So, you in room X, and you go north, and you get a message "you can't go that way" you mark the combination X/north as "no good". Then next time you first consult the table, and don't try to go north from X.

But say you can go north, but end up in a dead-end, and eventually back at X. You still mark X/north as no good because it failed, not initially, but eventually.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

Top

Posted by

Neurowiz (17 posts) Bio

Date

Reply #6 on Thu 24 Oct 2002 01:25 AM (UTC)

Message

OK, I've gotten some good suggestions and I think I'm ready to actually code this thing - it ends up being easier than I thought! (A good thing...)

I'll try and put something up here in about a week. Hopefully I will get it figured out.

Top

Posted by

Guest1 USA (256 posts)

Date

Reply #7 on Thu 24 Oct 2002 03:22 AM (UTC)

Message

You'll need to factor in things like 'unlock door east;open door east' as well, unless there aren't any doors on the mud you play :)

Take a look at Portal Client's mapping feature http://www.gameaxle.com/ it's pretty kewl. I think I brought this topic up a while back... anyway, I have not had a big play with portal, but they claim their mapper not only maps 3D, but can do exactly what you wanted: instantly travel from one room to another using their true shortest-path AI. Sounds very very kewl.

Other than that mapper feature, MC is still #1 imho.

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.

22,689 views.

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

Go to topic: Search the forum

top