Zugg Software :: View topic

Wanderer Joined: 06 Jan 2006 Posts: 70

Just thinking of map wishlist functions.

Maybe the ability to move rooms via function? Like instead of edit, move, down, apply. We could do a #noop %roomlevel(vnum, 0)

:-D

Posted: Tue Feb 14, 2006 9:04 pm

Have you checked the scripting functions in zMapper? I think there are already functions there to move rooms around.

Wizard Joined: 14 Aug 2004 Posts: 1269

Zugg, do you want us to put everything on our wishlist related to the mapper in this thread, another thread, individual threads for each one, a different forum, e-mail, or...?

Posted: Thu Feb 16, 2006 4:04 am

For now, either way is fine. Either this thread of in another thread. It will be several months before I'll start work on the improved CMUD mapper.

Newbie Joined: 28 Jan 2006 Posts: 4

I would love the ability to set custom costs of exits. ZMUD's mapper allows to set custom cost for entering room, but then they apply for all exits leading into the room - you can't change it for individual exits.

Adept Joined: 21 Sep 2005 Posts: 250 Location: Austin, TX

I'd go even farther than that - It would be very nice to be able to insert a custom path-cost calculation function that is called by the path-finding algorithm. That would allow users to account for a whole host of conditions that could change room costs, even on a moment-to-moment basis. Users could also adjust for 'danger factors', which don't actually impact the room costs, but would cause different route choices. For example, on my MUD (Mozart), SOME of the various considerations when I decide to travel are:

Mountainous terrain costs extra movement, however, if you have mountaineering skill, cost is lower. If flying or floating, cost is 1.
Travelling in water costs extra movement, however, if you have swimming skill, cost is lower. If flying or floating, cost is 1.
Travelling in some water rooms is impossible without a boat or a flying spell. Floating spell is not sufficient.
Certain areas have aggressive mobs, but those mobs cannot see invisible players. (This is an example of a 'danger factor' - if I'm invisible, I'd go through. If not, I'd go around). Other mobs will only attack players of certain alignments.
Certain rooms/zones are hot/cold/electric, etc. and cause hit point loss to pass through. It is possible to be immune to the specific effect in the room. (Another 'danger factor')
Some zones prohibit the use of portal spells (e.g. word-of-recall, astral-walk, gate). Some zones prohibit certain portals and allow others.

I'm sure I could list more, but this gives the flavor. All of these and a host of other factors (e.g. exit costs) could be dealt with using a custom step-cost function. Most could be dealth with NOW by looping through the DB and resetting room costs every time a condition changes.

What I don't know is if this custom-function approach is feasible. Using a custom (interpreted) function in the pathing algorithm might be unacceptably slow. The only other approach I can think of would be to have a hook for a user-defined function that gets to run just before a path is calculated for any reason (whether by double-clicking the map, typing .<path>, or whatever). That function could loop through the map resetting costs on each room too.

Coder geek musing: I presume the thing uses a breadth-first search with all portals treated as potential first steps, and if it's clever it can prune at many zone boundaries. For non-pathological cases, I'd expect the number of calls to the custom step-cost function to be proportional to a low power of the path length (maybe O(num_steps^1.5) or less). The callback hook would obviously be O(map_size), but you could keep flags to see if conditions have changed since the last time you ran and trap out immediately.

Wizard Joined: 14 Aug 2004 Posts: 1269

I would echo jquilici. One of the things for my wishlist would be a custom path-cost calculation function too: on the MUD I play move costs vary by room sector and room flag (which are fixed so no problem here, but e.g. road sector and trail flags only work when you move in the direction of the road or trail (so like Shan's suggestion)), but also depend on whether you are riding or not, and what race you are playing, and also how much weight you are carrying and how much wilderness you have practiced, but these last two I probably wouldn't bother putting into a custom function. Climb exits and swim rooms should also have an extra danger rating, but swim is affected by if you are carrying a boat. If I have a boat, I'm pretty happy crossing a river, but if I don't I might go around, and if I have a horse that can't swim (no boat) or leading followers, I'll almost certainly want to go around.

I'll post other wishlist things here another time.

Wizard Joined: 25 Mar 2003 Posts: 1113 Location: USA

I agree! This is something I've wanted for a long time, especially if I share my maps with others whose costs to move about may vary. When I have my waterwalking shoes on, I don't need to swim. If someone else doesn't even have the ability to tread water, they may not want to go through water rooms at all. Terrain in the wilderness, such as moutains and tundra, is only difficult when I'm not flying. The list goes on, and it seems that cases like these exist on many MUDs out there. Some sort of custom exit cost would definitely be appreciated.

Posted: Sat Feb 18, 2006 12:22 am

I'm afraid that a custom calculation probably won't happen because you just won't like the results. The path finding algorithm computes the cost a *lot*. If anyone has ever coded a shortest path algorithm in school, then they are probably aware of how these algorithms work. But to give you a custom calculation would mean that the cost would be computed in a *slow* scripting function, instead of the current compiled function (which just returns a constant value for a room).

In other words, the path finding routine would slow down a *lot*. How much? I haven't tested it, but I'd guess that you'd be looking at something like a factor of 20 slowdown at minimum. So something that takes a second could take 20 seconds, which then makes path finding useless.

So, while a custom calculation probably just isn't feasible, stuff like a exit-dependant cost, or a cost based upon the room type is certainly more likely.

Wanderer Joined: 31 Oct 2004 Posts: 94

first off..

mmmmmm. CMUD :P

second off: mapper wishlist-

make the slow walk command a lot more integrated with the automapper. for example, when you use your map and double click a room, the path in your queue is overwritten. more importantly, your place is lost. Fortunatly, this wasnt THAT hard to script around in Zmud, provided you re-wrote your own slow walk system. Anyways, basically i'd just like to see these two systems not conflict with eachother. Maybe by allowing your character to walk more than one path and be able to toggle between them? Eh maybe this isnt even really a mapper wish. But i've found that i only need these multiple paths in use with the mapper.

UMDBANDIT

Adept Joined: 21 Sep 2005 Posts: 250 Location: Austin, TX

That's what I was afraid of (as I mentioned above). But you never know until you ask. Wink

Magician Joined: 09 Oct 2003 Posts: 459 Location: USA

is there a binary plugin interface for zmapper? Twisted Evil

SubAdmin Joined: 18 Nov 2001 Posts: 5182

There might actually be a way to do a custom cost without the drastic slowdown. If each cost point was allowed to have say 8 different flags. Each flag could then have a multiplication factor assigned to it map wide and a table could be prebuilt for all the combinations possible. A mask of flags could be set by the user within triggers, and then the calculation is an AND followed by multiplication from the prebuilt 256 integer table with the move cost of the exit or room. This allows adjustabilty while only adding about this much to the code within the calculation:
MOV EBX,[ESP+232] ;Fetch mask from stack
AND EBX,[ESP+16] ;And flags specific to link
MOV ECX,[ESP+12] ;Fetch table address from stack
MUL EAX,[ECX+EBX] ;Multiply link cost by table value

Total 4 opcodes 16 bytes. Assuming the use of register flags on the variables and a guess of what pointers you would use.

Wizard Joined: 14 Aug 2004 Posts: 1269

Didn't completely understand Vijilante's post, but I was thinking of a way of doing a fairly customisable path-cost calculation.

I'm thinking of an object-oriented approach where rooms inherit from their room kind and exits inherit from their exit kind. Rooms and Room kinds can inherit defined room flags (both pre-programmed in CMUD, e.g. "do not enter", and user-defined) and Exits and Exit kinds can inherit defined exit flags (both pre-programmed in CMUD, e.g. "locked door", and user-defined).

Let's say that a room can have several properties relating to movement: room kind, do not enter, additional room flags, and additional room cost (over and above the room kind cost and room flag costs). Exits can have several properties: one-way, door, locked door, exit kind, additional exit flags, and additional exit cost (over and above the exit kind cost and exit flag costs).
Room kinds have several properties: graphic, base move cost, user-defined-1, user-defined-2, ... user-defined-5.

Exit kinds have several properties: graphic, base move cost, user-defined-1, user-defined-2, ... user-defined-5.

It would be possible to have more than 5 user-defined flags for rooms, but not have more than 5 on any one room kind or room, so, e.g. you could have 5 on mountain rooms and 5 on inside rooms, and only two of these would be the same flag. Same for exits. This is to enable the speed walking algorithm to have a fixed number of variables, to enable it to be compiled. (If this isn't necessary to compile it, skip the restriction.)

room-user-defined-1 (rudf1), etc. can be set to have a name (for displaying in the room properties), description (just for remembering what it is for), base move cost, move cost multiplier variable name, add move cost to room or multiply with total room move cost (toggle), command-before-entering. The move cost multiplier variable is the name of a CMUD variable to muliply the user-defined base move cost by. The command before entering is a single line to pass to the MUD or an alias. For example, I might set rudf1's name to Swim, the description to "Add this property to rooms or room kinds that require swimming.", the base movecost to 1, the multiplier variable name to SwimCost, add move cost to room, and the command-before-entering to "swim on". Maybe swim would be an alias which checked to see if the MUD thought we had swim switched on, and if the parameter was on and the MUD had swim off, sends the command "~swim on", and vice-versa. Now a new character with no swim ability would want @SwimCost set to 1000 so we avoid swim rooms altogether. A character with swim ability of 50% might have @SwimCost of 5, or with 100% ability: 3. It would then possible to make triggers like:
"You get a canoe." --> #VAR CharDefSwimCost @SwimCost;#VAR SwimCost 1
"You drop a canoe." --> #VAR SwimCost @CharDefSwimCost
So by getting or dropping a canoe, the path finding algorthim will choose different paths, but I don't think this needs to be interpreted does it? The algorithm can be hard coded, but with extra variables.

Similarly, exit-user-defined-1 (eudf1), etc. can be set to have a name (for displaying in the room exit properties), description (just for remembering what it is for), base move cost, multiplier variable name, command-before-leaving-through-exit. For example, I might set eudf1's name to Climb, the description to "Add this property to exits or exit kinds that require climbing.", the base movecost to 1, the multiplier variable name to ClimbCost, add move cost to exit, and command-before-leaving-through-exit to "climb on". Now a character with no climb ability would want @ClimbCost set to 1000 so we avoid climb exits altogether. A character with climb ability of 50% might have @ClimbCost of 5, or with 100% ability: 3. If you were flying, you might set it to 0.

On my MUD, I would also create exit-user-defined's of TRAIL and NO_RIDE. NO_RIDE (non-rideable) would have a command-before-leaving-through-exit of "lead", which is what I use for dismounting and leading my mount (actually an alias with conditional code in is probably what I'd use), a base move cost of 0 (I'll deal with that in a room-user-defined), and no move cost multiplier variable name. TRAIL would have a base move cost of 0.5, no move cost multiplier variable name, since it will be a constant multiplier, and multiply with move cost (since I want to half the move cost of room linked by trails).

I would also create a room-user-defined's of WALK, RIDE and NO_RIDE. WALK and RIDE I would add to all room kinds that can normally be walked or ridden. NO_RIDE I would add to individual NO_RIDE rooms and would have a move cost multiplier that produced a result equal to the difference between the walking and riding move cost for that room kind - in order to use only variables here and not functions (so as not to slow things down), I would need separate NO_RIDE room-user-defined's for each room kind.

For the @RideCostMultiplier, I would set it to 0 when I wasn't riding, 1 if I'm riding but not very good at riding, 2 if I'm not good at all, etc. For @WalkCostMultiplier I would set it 0 when I was riding to eliminate the walking costs, or 1 when I was walking. In addition, when walking I would need to set the @NO_RIDECostMultiplier to 0, since it doesn't apply (as I'm not currently riding).

I think that's about all I would want for my MUD (except for a SLOPE exit flag and I might tweak a few things for different races), and I think it's generalised enough that it should work for any MUD. So if your MUD had flying, you would simply set @WalkCostMultiplier to 0 when you started flying. I can't think of a use on my MUD, but some MUDs might have a use for command-after-entering-room and command-after-leaving-through-exit.

Of course this may be quite a lot of work for Zugg to implement, especially as there would probably need to be an interface for configuring the user defined room and exit flags. I expect this would have to be in CMUD-Pro only. But there are other benefits to this than just speed walking shortest path calculations:-

The inheritance model would allow graphics to be overlayed on each other if the graphics are transparent, so a trail_flag graphic could be overlaid on a forest room_kind graphic, and a NO_RIDE or "Do not enter" graphic could be overlaid on any room.

The ability to generalise rooms would mean you could effectively have a script called when you entered a room kind, rather than just a room, or an exit kind. So it means a lot less room scripts (e.g. the door exit kind might have as the command before leaving: "MapOpenDoor" - this would be an alias which tried to open the door and dismount).

It would mean a lot less tweaking of each room to get the Move Cost right, since most things could be inherited from the room kind or exit kind.

Seb

Wanderer Joined: 06 Jan 2006 Posts: 70

GURU Joined: 10 Oct 2000 Posts: 873 Location: USA

Wanderer Joined: 06 Jan 2006 Posts: 70

Or zMapper could just make exit cost count as invisible rooms if you get me. Like an up exit that costs 4 would just create 4 rooms 'temporarily' and calculate normally.

Posted: Thu Feb 23, 2006 7:01 pm

Seb, yes, that's more like I was thinking. zMapper already implements an inheritence type of object system for room types and link types. All I need to do is add costs to links and then add ways to use the custom flags in the calculation, similar to what Vijilante posted.

What I need to avoid is calling a "script" to calculate any cost. Tarn, even caching the cost per edge is very expensive when calling scripting. And you can't do it in a seperate thread because of memory sharing issues with the scripting engines that are not thread-safe (I learned the hard way about that in zApp). I've got a lot of experience now with scripting from zApp and any sort of scripting call would make the path algorithm way to slow.

But I think there are still ways to improve this without using a fully custom script for the cost. Only a *very* small minority of people would use such a script, and I think most of the issues that have been mentioned can be handled as already described.

Definitely something I'll be looking into for the CMUD mapper.

Novice Joined: 21 May 2004 Posts: 32

Maybe scripting is slower through the scripting host than through a native script interpreter, but I think you should consider attempting a proof of concept for a custom cost function. I'm not so sure the speed will suffer that much, specially considering the recent speeds you have shown for a simple compiled script.

Let me contribute some anecdotal evidence for why I think the speed would be reasonable using compiled script functions: A while back I adapted the A* algorithm to solve a 2d 4x4 puzzle similar in concept to a Rubix cube though with a few differences. I did this in Python, and it finds a solution after about 1600 iterations in just over 1 second (about 3 seconds if I don't use Psyco to speed up the code). Due to the nature of the problem the metric function I used is a bit more complex than most typical cases that have been proposed for cost functions -- if flying set cost = 1 elseif no boat set cost = infinite and so on. Although it is possible that due to the nature of CMud being a more complex program the overhead will contribute quite a bit more than my stand-alone script.

A possible compromise might be to only flag some rooms as having a custom cost function, so depending on the types of areas, the path-finding might not take much longer than it does now, although the worst-case condition might end up a few orders of magnitude slower.

Wizard Joined: 14 Aug 2004 Posts: 1269

At the end of the day though, putting more cost calculation stuff in the GUI will ensure it gets used by more people than allowing a completely custom cost calculation function.

Posted: Fri Apr 07, 2006 6:43 pm

Also, you misunderstand the speed comparison. Yes, compiled scripts are faster than interpreted scripts. But that's still 10 times slower than actually coding the function in Delphi and compiling it into CMUD. Compiled scripts are not executing Intel machine code...they are still executing an intermediate code. So it's not at all the same as what we are talking about here.

Trust me, I *have* spent a lot of time speed optimizing the speedwalk algorithms. Anyone that has been around here for a while will remember all of the optimizations that were done several years ago when the mapper was rewritten completely to use a database. The speedwalk algorithm is on a very fine line...even a factor of 2 in speed makes it almost totally unuseable. Remember we are talking about maps with hundreds of thousands of rooms with an unknown number of exits and portals in each room, with loops and one-way passages. This is much more complex and time consuming than a rubix cube solver. And I'm not going to waste time on a feature that ends up being completely worthless when I'm done.

I think other people in this thread have suggested many wonderful ways to provide as much flexibility as you'd need without needing to have a completely customized cost function.

Magician Joined: 29 Nov 2005 Posts: 482

I can say this. I would like to see PATH ROUTING.

We have areas called CHAOTIC PLAYER KILLING where if you are killed you drop your equipment and it can be looted. We have PK ZONES all over our mud and there are times that running a path can be annoying hard due to the mapper. It wont re-route around the PK rooms and find a "SAFE" path it just picks a path and runs and they arent always the same paths. I can do it 3 times and get 3 different routes. I would like a way that has a "SAFE" runability

As to costs i do that through scripts anyways it would be nice to see but then you have to add terrain types and costs associated with them and define them for your mud. Each mud has different terrains and costs depending on how you are doing it. For example i can magic carpet across water i can walk i can walk levitated i can use a ship each has its own cost associated and this is complex i think for zugg to do to encapsulate the majority of mud systems. Im sure there is scripting alternatives to handle that

Magician Joined: 23 Nov 2004 Posts: 364

#call %roomcost( 1361, 9999)
#call %roomcost( 5860, 9999)
#call %roomcost( 137, 9999)
#call %roomcost( 1081, 9999)
#call %roomcost( 588, 9999) and so on

set that up in an alias, say pkon, and set the 9999's back to 0 for an alias pkoff, then when you are speedwalking you will avoid the pk areas if you don't want to be in there and take the slower route, and if you want to take the fastest route you can just type pkoff.

GURU Joined: 23 Dec 2000 Posts: 4834 Location: USA

Beginner Joined: 18 Aug 2005 Posts: 15

Maybe I'm flying ethereal kites here (from a development point of view, i know how I would do it, but I have never touched Delphi - Although I ended up eventually moving to .NET, for a long time I clung to pure C++ coding, and abhored Borlands C++ Builder, so avoided Delphi like the plague).

Anyway, for room-exit cost calculations, the problem seems to be that it would have to re-calculate them A LOT, and therefore there would be an unreasonable slow-down every single time it had to run through the whole lot. My solution to this would be:-

a) You flag/register a variable as a 'Mapper-Affect'. This would add it to an internal cluster/list of variables. The list itself has a flag associated with it, so if one of the variables in the 'Mapper-Affect' list is changed, the list gets marked as dirty.

b) When plotting routes (or maybe once in a while if multi-threaded), the Mapper checks the status of the list of variables it'll use in the calculations. If the List is 'clean', nothing has changed, so it can use the calculations it already has. If the list is dirty, it runs the exit calculations again. (this could be refined even more with interim user-defined sub-calculations, so rather than running the same calcs over and over per room, it many of them could be done one for the first room with that type of exit, then the result known to all other rooms with that type)

Anyway, just 2 hap'orth,

Yours,

Ann-Marie

P.S. I'm one of those who scripts ZMud a lot, but often only browses the forums rather than posting - and what ever else anyone says about CMud, and even though i loved the free ZMud upgrades for a loooong time, I'd happily pay full price regardless for CMud, not only for what it contains, but because I'm also in Zugg's boat, and I'd want him and Chiara to be able to keep producing such wonderful software - I've been caught in the same situation as Zugg has.