30 Aug, 2011, Rarva.Riendf wrote in the 1st comment:
Votes: 0
I am in the current process of multithreading the track command as it can be very cpu intensive.
I was wondering if anyone did it properly before reinventing the wheel.

My first step is to launch it by passing char_name instead of a pointer to char that could quit while the track thread is still computing the path.

Then to create yet another update method that would check for the threadresult and then show it to the char provided he is still there.

So how have you done it ? (if you did…)
30 Aug, 2011, KaVir wrote in the 2nd comment:
Votes: 0
I assume you're talking about a GPS-style "tracking" system, using a pathfinding algorithm to find the shortest route from X to Y?

In my mud this is extremely straightforward, because I don't use rooms. I can simply take the x/y positions of the starting point and the destination, and calculate the distance and direction from those. The shortest distance between two points is a straight line, after all.

In a room-based mud it can start to become CPU intensive if you're calculating long paths from scratch. One way around this is to precalculate common routes, and link people to the closest route (although this doesn't guarantee the shortest route). Another option would be to precalculate the routes between area entry points, so that (for example) if you're in Moonhaven and you want to find someone in Witchwood, the mud only needs to calculate the shortest route from you to the edge of Moonhaven, and between your quarry and the edge of Witchwood - the routes through the areas in between will all have been precalculated.

I once played around with a pathfinding "track" snippet, back when I was working on the original God Wars, but as well as being a CPU hog I also didn't feel it really captured the concept of tracking - if someone went north, then east, then south, surely if I were following their tracks then I'd go the same route? Yet the track command would just tell me to go east (assuming the appropriate exits were in place).

So I created a much simpler solution. Each room stored the names of the last few people who had passed through, along with which direction they had left. If a lot of people had passed through the room after your quarry was there, the tracks were assumed to have been trampled over - although you could move around and try to pick up their trail again.

I don't think I did much more with the concept, but in theory you could factor in terrain (making it easier to track people through mud or forests, very difficult to track through rivers, etc), weather (rain could wash away tracks), etc. The quarry might also be able to backtrack, leave false trails, etc. This is much easier to implement than a decent pathfinding algorithm, adds various interesting gameplay opportunities, and avoids turning rangers into GPS-guided missiles.
30 Aug, 2011, Rarva.Riendf wrote in the 3rd comment:
Votes: 0
Well I am talking about track but I also have a function I named path that calculate a route between the room you are in and the room you want to go in (provided you already explored all the rooms in between) (and that use track snippet) It is like consulting the map you drew while exploring.
(acts like a teleport but makes you walk, with all the thing that could happen and interrupt you (aggro mob, traps etc)
I allow this command to work for the whole world (ie you can be on the edge of it and ask for the room on the opposite, it can really stall the whole mud)
It would be best done in another thread.
Multithreading stuff asynchronously can be a bitch and full of traps, so I prefer to ask before I start doing it.

I think most muds limitate tracking to the area you are in, so it never gets too many rooms to parse.

And If i want to keep only using rooms the player has explored, I cannot really precalculate paths.
30 Aug, 2011, KaVir wrote in the 4th comment:
Votes: 0
For something like a city, I think it would be fine to precalculate routes between (for example) each room and the market square. Then if someone wants to go to the baker, or the blacksmiths, or the alchemy shop, or the east gate, etc, you can give them directions via the market square - perhaps checking whether the route passes through their current room to avoid them doubling back on themselves.

But if you want it to cover the entire world, and only use rooms you've previously explored, it really sounds like something that should be done by the client. In fact several clients already support exactly this functionality through their mappers. Handling it all at the server end is going to involve a fair amount of number crunching.

I guess you could do it in another thread. Or if you really want to avoid multithreading, you could have a separate process that communicates directly with the mud, and uses its own copy of the world data files to calculate the best route and report back. Personally I'd just let the client handle it though.
30 Aug, 2011, Rarva.Riendf wrote in the 5th comment:
Votes: 0
Quote
Personally I'd just let the client handle it though.

Thing is automapping is not always easy for players to use. It involves configuration, scripting etc, and is not always implemented at all. I agree it would be way better to have them do it but heh, I also have a 'share map' command hard to share map when you dont use the same client as well (and merging two players map not really easy).
The way to go would be to customize a client like you did and have all the players go throught it.
30 Aug, 2011, David Haley wrote in the 6th comment:
Votes: 0
The search shouldn't be CPU intensive. If it is, your search algorithm might be borked, or your search state data structures aren't very good. (For example, you might have a good algorithm, but have linear-performance lookup rather than constant or logarithmic.)

What kind of tracking are you looking at? Can you track somebody across the entire world? Just fifty rooms?

You can think about adding some basic heuristics. You could precompute a rough estimate of a room's coordinate from some known center-ish location by walking out from the center and finding the shortest path, and use that to assign a coordinate. You would use this to guide the search in the "right direction" – if you can guess that the victim is east based on the coordinate estimations, you should probably search more east than west. This could be used to guide an A*-like algorithm, for example. Obviously the estimates aren't perfect, but they should be ok enough.

Anyhow, if you specify more precisely what the requirements are and what approximations are acceptable, and what the bounds are, you could do something like this without multithreading.

Just think of the utter headache that threading will introduce. Every single one of your routines that edits rooms will need to have locking – you can't be editing the room graph while trying to compute a path through it. Same for a room's person list. And then you'll have to deal with all the ugliness of asynchronous command results… it's just going to be a headache, that can be avoided entirely with a little bit of thought in your search algorithm.
30 Aug, 2011, Rarva.Riendf wrote in the 7th comment:
Votes: 0
David Haley said:
The search shouldn't be CPU intensive. If it is, your search algorithm might be borked, or your search state data structures aren't very good. (For example, you might have a good algorithm, but have linear-performance lookup rather than constant or logarithmic.)

Have no idea as I did not implement it, but I think it is the basic track (recursive) algo you find in the repository here:
http://www.mudbytes.net/index.php?a=file...

Quote
What kind of tracking are you looking at? Can you track somebody across the entire world? Just fifty rooms?

Whole mud so around 14k rooms atm.

Quote
You can think about adding some basic heuristics. You could precompute a rough estimate of a room's coordinate from some known center-ish location by walking out from the center and finding the shortest path, and use that to assign a coordinate. You would use this to guide the search in the "right direction" – if you can guess that the victim is east based on the coordinate estimations, you should probably search more east than west. This could be used to guide an A*-like algorithm, for example. Obviously the estimates aren't perfect, but they should be ok enough.

Well I could look in another algo for sure, especially if you tell me than the onde provided sucks, and then next question would be:has anyone written one in C :)
Maybe something like this?:
http://www.boost.org/doc/libs/1_47_0/lib...
or this:
http://en.wikipedia.org/wiki/Lee_algorit... (though at first glance it looks like track is written like this)



Quote
Anyhow, if you specify more precisely what the requirements are and what approximations are acceptable, and what the bounds are, you could do something like this without multithreading.

Acceptable would be not stall a ROM base code if you asked for the path from far east to far west of the realm , that could be around 100 room.

Quote
Just think of the utter headache that threading will introduce. Every single one of your routines that edits rooms will need to have locking – you can't be editing the room graph while trying to compute a path through it. Same for a room's person list. And then you'll have to deal with all the ugliness of asynchronous command results… it's just going to be a headache, that can be avoided entirely with a little bit of thought in your search algorithm.

Heh, that is why I asked the question before I really started to code. I would not code it totally safe anyway (I would only make it safe from player commands). for imms, I would just disable the command itself before lauchning some commands.
Multithread is really the last solution I want to go in, but I feel that whatever the path finding algo, it would still be too slow if enough player use it. But maybe I am wrong.
30 Aug, 2011, David Haley wrote in the 8th comment:
Votes: 0
Well, the algorithm does a number of silly things, although it's not disastrous. First of all, it shouldn't be iterating over a room's exits if that room has already been visited. It should test for the room in the table as soon as it takes it off the queue, rather than testing if a destination room has already been visited before processing it.

I can't guess if the hash function is any good (multiply by 17, modulo table size) but it would be worth inspecting how good of a hash function that is (i.e., how many collisions there are).

The part that looks up the item in the hash is borked, though. The hash functions already handle collisions. The search code has no business trying to do its own handling, especially when that handling is borked. If it doesn't use the same collision resolution, how is the next lookup supposed to find it? Further: it's doing silly things like calling the same function twice.

The thing about functions like this is that the high-level view might be the same, but the devil is in the details of implementation. If you use a hash table to store where you've been, but the hash algorithm sucks, then your algorithm will be very slow.

Quote
Acceptable would be not stall a ROM base code if you asked for the path from far east to far west of the realm , that could be around 100 room.

That wasn't really the question, though. What approximations are acceptable? What if I return a path that is 25 steps long, but the best path is 22 steps long?


See, the thing with search functions is that if you blindly explore the whole space, then yeah, it'll be slow because you have no idea how to help the search. If you can give it even a little hint, provided that the hint is actually not a terrible one, then you can speed things up drastically.

Consider the difference between blind breadth-first search, and a slight modification that tends to explore nodes that seem to be in the right direction before nodes that seem to be in the wrong direction.

Quote
for imms, I would just disable the command itself before lauchning some commands.

This sounds like asking for trouble if you ever have some kind of live building, but that's your call to make. :wink:

Quote
Multithread is really the last solution I want to go in, but I feel that whatever the path finding algo, it would still be too slow if enough player use it. But maybe I am wrong.

A good pathfinding algorithm will tear through search spaces. The issue here isn't the size of your search space (which is, honestly, tiny); it's the method of search.

To give you an idea, I once wrote a program that, given a description of the rules as logical axioms, perfectly plays Tic Tac Toe and solves the whole game in a few seconds using a logical theorem prover for every state. Tic Tac Toe has some 5.5k states, so your 14k rooms are nothing considering that you don't have to run theorem provers at every step of the way.

So again, the point is that you should try to search smart before you resort to dangerous and complex tricks like multithreading.

What do you think of the coordinate heuristic idea? Again, the question is what approximations are acceptable. Is it ok if the answer returned is not perfect? My suspicion is that that's just fine, because if you're 100 rooms away, you don't really care about more than just "in that direction". In fact, you might not even have to search if you use approximate coordinates: given two coordinates, it is trivial to say what the general direction is. It just depends on how accurate those approximate coordinates need to be.
31 Aug, 2011, Davion wrote in the 9th comment:
Votes: 0
If you want to look at an active implementation of a tracking algorithm that uses BFS check out shadowstorms map system. Should be called GetPath. Drawing the map also uses the same algorithm. Pretty fast too.
31 Aug, 2011, Runter wrote in the 10th comment:
Votes: 0
Quote
I feel that whatever the path finding algo, it would still be too slow if enough player use it. But maybe I am wrong.

You are indeed wrong. I suggest you profile some pathfinding code and see how long it takes. Even the worst algorithm should be fine for your use case. Especially in C.

I don't like multithreading here. I could go into the litany for reasons why. But if I were going to do it, I'd a Redis list, a Redis map, and a Redis subpub channel.
http://redis.io/

First of all, you have to either lock the search areas data. (As in it can't be modified until the search is done.) Or you need to copy it into a temporary structure. Or you can just roll the dice that a multithreaded solution won't ever be a problem if your world structure stays the same most of the game. This is what most people do, and it's wrong.

I'd subscribe to the channel using the main thread to listen for the finish. I'd start any number of worker threads in the seed room. I'd use the list to feed the workers. I'd use the map to determine which nodes have already been worked on. Each worker would subscribe the channel for the job. Workers would emit a message when the list is populated so other workers know to continue. I'd then have the tail worker publish the result to the Redis pubsub channel.
31 Aug, 2011, Rarva.Riendf wrote in the 11th comment:
Votes: 0
Quote
So again, the point is that you should try to search smart before you resort to dangerous and complex tricks like multithreading.

Considering all you said, I think I will indeed start to review the pathfinding code. Willl try Davion one.

Quote
You are indeed wrong. I suggest you profile some pathfinding code and see how long it takes. Even the worst algorithm should be fine for your use case. Especially in C.

Well the code I have in currently is definitely not good enough for my need :) But considerint how you pretty all say the problem is there, I will indeed look into it, I have done enough multithreading in my life to know how a nightmare it can be.

Quote
First of all, you have to either lock the search areas data. (As in it can't be modified until the search is done.) Or you need to copy it into a temporary structure. Or you can just roll the dice that a multithreaded solution won't ever be a problem if your world structure stays the same most of the game. This is what most people do, and it's wrong.

Players cannot modify the areas, only imm can, as I said to Davion, I would simply disable the command and wait for any thread alive to finish before an imm can build anything (building anything should be done in a building port, the only live creation I do is generating maze automatically but this is again a imm command). But…I still prefer to avoid multitheading if I can.
31 Aug, 2011, quixadhal wrote in the 12th comment:
Votes: 0
Rarva.Riendf said:
Players cannot modify the areas, only imm can


Are you sure?

Consider that opening and closing doors may modify your path. Locking and unlocking them certainly would if the player/entity finding a path doesn't have a key or way to break the door down.
31 Aug, 2011, Runter wrote in the 13th comment:
Votes: 0
Any data the search depends on must be locked. Including possibly things like… player lists for rooms that can only contain a 1 person at a time… player lists for when your target is a player in a room. In general you completely lock resources not only for the current use case but for being safe for future development. It becomes very difficult to keep up with resource dependancies.

Pathfinding algorithms in general must account for some of these things. I think it's easy to hand wave away the problem by saying that you know the area can't be changed by players. Some games have rooms that have changes all the time without being edited. I've seen muds with areas that can rotate 90 degrees to make it face a different direction, for example. Weather systems that can erode paths.
31 Aug, 2011, Rarva.Riendf wrote in the 14th comment:
Votes: 0
quixadhal said:
Rarva.Riendf said:
Players cannot modify the areas, only imm can


Are you sure?

Consider that opening and closing doors may modify your path. Locking and unlocking them certainly would if the player/entity finding a path doesn't have a key or way to break the door down.

Yes I am sure as the path I give from a map does not mean in any way that all the door will be open. It is like reading a map in a car. In no way are you sure a bridge or a road wont be closed: it only means that, one day in history, you could go through it.
Your concern (and Runter one) are valid in an use case that is not mine.
The thing I have in mind is:you explored xyz map, drew a map out of it, and want to go from x to z: you look at your map draw a line and then try to follow it, tough luck if it needed a boat and you dont have one or need to be flying and you are not, it give you the path as if you coudl take it again, does not mean you can take it in the condition you are (you could have not enough moves anyway).
Only forbidden thing is you teleported to x, teleported to y, and then rty to walk between the two rooms(touch luck yu have no idea how to do it)

For this I already store all the rooms you visited (storing vnums you visited basically, as bits). The only random areas are disconnected from the 'stable' realm so you cannot 'walk' to them.

So yep it is a lot simpler than what you have in my mind, so have to lock a lot less thing.
And well, will test some new pathfindnig algorithm first, as even if I do not risk a lot multithreading considering what I want to do, it is still easy to fall in a trap (all the points you raised are totally valid ones) when you add multithreading in an after thought.
02 Sep, 2011, Rarva.Riendf wrote in the 15th comment:
Votes: 0
BTW, I thank you all for hinting that a path finding should be fast enough to not require multithreading. Indeed, I identified the real culprit of the bottleneck:
Instead of storing the path while it is calculated previous coders had the horrible idea to calculate path, move the first room in it, recalculate path from there, till it find the last room…hugh.
02 Sep, 2011, David Haley wrote in the 16th comment:
Votes: 0
That isn't necessarily a horrible idea… it's actually a good idea if your world exits can change (e.g., doors). In your case, though, this is wasteful given that you've said your world doesn't change in this way.

Besides, a reasonable pathfinding algorithm should be pretty darn fast even if you were recalculating it from scratch after each move. (Consider RTS games with hundreds of units navigating the game map, each requiring pathfinding.)
03 Sep, 2011, Rarva.Riendf wrote in the 17th comment:
Votes: 0
I see your point, but I was not clear enough :)
It is not calculate path move char recalcluate path. (that you should indeed do if your world can change)

It was calculate full path, but only store first direction, then virutally go in this direction calculate full path, till you arrive THEN cumulate all the direction to get the path :) THEN make the char move :)
03 Sep, 2011, kiasyn wrote in the 18th comment:
Votes: 0
an interesting way to tackle this would to just store footprints/etc in each room.

a skilled ranger etc would look for these signs and they would be displayed in the description. it would also mean you could throw people off your track by walking into rooms unnecesssarily.
03 Sep, 2011, Runter wrote in the 19th comment:
Votes: 0
I don't see what's wrong with just using an A* search and the manhattan heuristics method. All this "store the first in right direction" business is a really bad instrument. Every step along the way it should be selecting the most likely search route up until that point by using a heuristic. I dunno about you, but I know on my games plenty of times you have to go a step west before falling a path that eventually gets you to the east. There's no reason to bet the farm on every permutation of routes to the east first.

http://en.wikipedia.org/wiki/Taxicab_geo...
http://theory.stanford.edu/~amitp/GamePr...

That's all if you're hellbent on all this coprocessing. Muds don't really need it. Muds in C definitely don't need it. You're not traversing a 44,000 element grid. You're probably traversing a < 100 node graph. If I really have to point to all the games out there written in higher level languages doing a straight BFS I will. You're going to need literally hundreds of players doing the search constantly before it would become an issue.

On haikumud I'm so unconcerned with this problem that (in Ruby) I use a BFS & I access the database multiple times every node. I'm probably running 50 times slower than what you'd get in C using immediate in-memory objects. And profiling shows no sign of it being too slow.
03 Sep, 2011, Runter wrote in the 20th comment:
Votes: 0
kiasyn said:
an interesting way to tackle this would to just store footprints/etc in each room.

a skilled ranger etc would look for these signs and they would be displayed in the description. it would also mean you could throw people off your track by walking into rooms unnecesssarily.


I agree that this would be a good way of solving the problem. I particularly like from the gameplay point of view the idea of "travelling light" making you more difficult to track. Both carried items & size of party at first glance appear to be great. Instead of talking about implementation I'd like to talk about overall design for a moment. I agree with KaVir's post a few back that track makes no sense just showing you the quickest path to them.

I wouldn't show a description of any type of artistic value. I'd probably allow a player to lock who they're tracking.
>track kiasyn
"You'll track Kiasyn for a while."

Then when you walk into rooms with the tracks it could perhaps give you a quick indicator on the map, if the game uses such a thing. Like arrows up to X room away depending on how easily they're able to track. This could make integration for players who are concerned about being able to make use of the feature in a realistic way possible. Also line of sight could be used for determining how far on the map the tracks should be shown.

If no mapper it could be a simple after the description or exits descriptions.
"NORTH is the direction the track leads."

Depending on your track skill when you hit intersecting tracks (old tracks in a different direction than the tracks you're following) you could have a chance of getting following the wrong path. Again, depending on your tracking skill you should have a chance when examining the tracks again (or entering a new room, autoexamine) that you get either:
"You've made a mistake tracking Kiasyn."
or the message you'd expect not realizing it's an incorrect path.
Also when there's no intersecting paths I'd make a chance for failing the track.

I'd be very concerned with the system being friendly for the tracker. If it's absolutely a nightmare trying to stalk someone successfully it won't be used. People will just run around the limited area til they find the person they're looking for. With good reason, most games don't have any downside to this type of wasteful movement. And knowing that the person you're stalking can run without limitation or lag, it makes tedious tracking seem not very useful…unless perhaps they don't know you're tracking them.
0.0/61