Member Discussions

Alright, I just read most every post on the advanced coding/design board that looked interesting, and one thing really caught my attention and made me start thinking about how I would implement it.

How do I make a mob who knows how to get from A to B?

Not just have a set routine, I can do that easily enough, but... lets say, I have a mob (or group of mobs, but I have no immediatly forseeable problems with group mentalities, so Ill keep it simple) that, for some reason or another, wants to hunt down and kill a player.

I have read up on the A* pathfinding algorithm [ http://theory.stanford.edu/~amitp/GameProgramming/ ] and have decided that this is certainly what I should use... if my MUD was coordinate based. Pretty standard set up, each room has a set of exits (with an 'arbitrary' name) that links to another room.

My first couple thoughts on how to handle the problem realistically proved unfeasible. Rooms would remember the last X number of players/NPCs who passed through, and with sufficient skill you could determine who went which way [track skill], and/or mobs would similairly remember the last X number of PCs/NPCs, and could be questioned [assuming no blatent problems with alignment, etc. also, this gives a use outside of haggle for a charisma score - something many dnd people are familiar and comfortable with]. But, I decided against both of those for the obvious reason of "oh god the memory!"

The best way I have thought to handle automated mob movement [and this does not include things like hunting players] is to have "nodes" [I am not sure if this a proper use of the term, please forgive and correct me if I am in error]. The general theory is that the mob would find its way to the room acting as a node. The node would act as a database, it would have a list of all possible locations the mob could want to go to, then it would direct the mob to either the nearest node closer to the destination, or it would send the mob directly to the destination if it was close enough.

The mob could find itself to the node through one of two approaches - brute force a pathfinding algorith (check every exit, and if the exit doesnt lead back to a previously explored room, check every exit, etc) until it finds a node, or, every room has a single direction which is flagged as leading to the nearest node. So the mob might move into a room, see south is the desired direction, go south, see east is the desired direction, go east, reach a node, then move [worst case scenario] north and west until it reached its destination.

While I could implement that system with relative ease, it still isnt as appealing as automating the entire thing. Perhaps give each area a coordinate, have the mob brute force its way [note, im not talking about the mob erroneously moving about, but rather running a simulation which has no visible in game effect asides which way the mob moves] from its current area to another, more favorable, area. And once there, the mob can rinse and repeat, until he gets to the desired area, at which point he can seek out the destination via brute force. While it isnt a very elegant solution [and will only result in finding the most efficient path to and from areas and, finally, to the mob from the last area change - but efficiency is a secondary concern], reducing the scope of each individual pathfinding attempt certainly makes things alot more feasible.

I was also thinking that the track skill could be similiarly limited. Perhaps have each area remember the last time a PC entered/exited it, and have the track skill based off of that [you dont know where they are, but you know that he last left this area 10 days ago, after staying for a while, and left northwest. or, if hes in the area, you can brute force a path to him.]. Or, perhaps, have other abilities attempting to discern a PC's location tell you thier general direction based off of relative area locations [ie, a mage might not be able to see his target, but intuitively knows that its NE of here] or even possibly give you a path to follow, connecting the areas until you arrive where you wish to be.

Any thoughts on this?

(Comment added by Sekket on Wed Feb 2 5:07:12 2005)

Um, incase you dont want to read through that stuff about A* (and something tells me most of you dont) try going here: http://www.ccg.leeds.ac.uk/james/aStar/ Select the map fails.grd (should be near the top) and hit start once its loaded. Changing between the different methods should give you a good idea of whats going on.

(Comment added by Sekket on Wed Feb 2 5:24:09 2005)

Um, incase you dont want to read through that stuff about A* (and something tells me most of you dont) try going here: http://www.ccg.leeds.ac.uk/james/aStar/ Select the map fails.grd (should be near the top) and hit start once its loaded. Changing between the different methods should give you a good idea of whats going on.

Great link, thanks!

I too am trying to figure out pathfinding at the moment... :)

(So sorry if you saw this reply and thought it was actually something helpful..!) ;)

I think it's really two separate answers you need.

The first is, how does a mobile (or even a PC, for that matter), negotiate from one known location to another over an unknown route. Ie, how does person_a get from River Square to Castle Entrance? This would require a determination algorithm to find the best path between the two locations which the user could navigate (either autonomously or with some input). I think this is the question you asked initially, but the criterion applied as samples for that question fall into the second one which should be asked.

That second question is: how does one find a person from a given location? Two factors can be used here. The first would be has that individual passed through the area where the seeker is, and if so, how long ago, etc. This would necessitate tracking of information on who has passed through where, when, etc. Not too memory intensive if you accept that it is not going to be possible to track everyone's every movement, and instead base the information you keep on the terrain, weather, etc - limit what each area can hold in terms of data, in other words. This allows those who have travelled through an area recently to be followed, while those who did it awhile ago (or a storm past) are lost and unfollowable. Other aspects of your game, such as notoriety of the trackee, could come into play in populated areas (the ground doesn't remember them passing through, but a townperson certainly does). The hive/group mentality that Brian Lindahl postulated in another thread could impact this, as well.

Although one could just use the first question to infer the answer to the second (Bob is at the Palace Gate, therefore I will navigate there), I think the better solution is the second. (I followed Bob's trail, either physically in the ground or by tracing his passage through the populated area and found that he was at the Palace Gate).

I never concerned myself with the first question, but did have a working solution implemented to the second on a previous MUD.

I did post that when I was a bit tired, but I can foresee some cases in which it is important for the mob to find its way to the player unerringly, as well as the certainly neccessary "I dont know where he is... how do I find that out?"

Good idea about having the multidimensional axis for trackability - I could certainly make it so that a Warder [fighter/mage class, heavily influenced by ranger] would have a tough time tracking someone through a city, while a Vagabond [general thief/rogue class] could do so much easily - and probably via asking about. Hell, I could even have some people with sufficient skill be able to attempt to start rumors for one effect or another.

The horde mentality [I believe] is exactly what I was referring to, and see a great deal of potential in the whole idea in general. So much so Im gonna post a link in hopes that those who are looking for a good idea will think it over - http://mudconnector.com/discuss/discuss.cgi?mode=MSG&area=adv_code&message=11305

Also, could I either be linked to that MUD in which you did this or told a bit more indetail how you tackled some of the possible problems with the design phase [or any particularly tricky coding aspects]?

Haha, well you keep it up and if you come up with anything good, come back here and share your inspiration, alright?

You should really check out this link though http://www-cs-students.stanford.edu/~amitp/gameprog.html as it has info on a wider array of subjects. Some of the offsite links can also provide a wealth of knowledge.

Thanks and goodluck.

I know this is extremely basic, but take a look at Pac-Man sometime. There are four ghosts. Each has a different set of instructions for how they will catch Pac-Man. The first two always try the most direct path possible. Basically, they go for as much of a straight line as possible.

Ghost three is trying to move away from Pac-Man. He is restricted to the area of the screen however, so will always remain within the area. Ghost four move randomly. They all act like Ghost three when Pac-Man gobbles a power pellet.

Normally what happens is Pac-Man will keep wanting to move away from the two ghosts that are directly chasing him. That's the natural reaction of most players anyways. This pushes him into range of one of the other two normally, and then all four ghosts can move in.

I know this example is rather simplistic, but I have found that simple is sometimes the best way for me personally to look at something. Later you may want to look at some of the extensive work done with scripting for an FPS, or just dive into the code. Stategy games are a great way to see how pathfinding is done as well. I hope you find what you are looking for, and have fun with it.

Yes and I could do that... but the problem is this: that is also on a coordinate plain. Mobs in my game do not have an absolute position on a map - it is unfeasible for me to make every room have a coordinate [ie, if you are at the origin and pacman is at 4,5 it is entirely possible [not likely, but possible] that moving southwest will put you ad the coordinate 4,6 and all you must do from there is move south... not a very pretty picture if the ghost continually tried to rush pacman]. Areas I can assign coordinates to easily enough, but individual rooms...

I think I have something that can work with the 'area by area' approach, though.

There are a few snippets out there as well for mobiles to find player characters. Most of these have to do with the mobile remembering a character and bearing some sort of grudge. I don't think most of those are what you are looking for however.

I have seen a few places where there was a track or tail type skill that sounds like it does what you are looking for. I've even seen spells where the caster summons a creature that could do the tracking for them. Most of these even work within the same area on room based muds.

A couple of snippets can be had from Mudmagic. I know that the Labyrinth codebase also has some tracking stuff as well. There are practical examples out there for how this has been done in muds before.

Um, incase you dont want to read through that stuff about A* (and something tells me most of you dont)

Well last time it came up there was this massive flame war between the BFS, DFS, Prim, Floyd, Djikstra and A* advocates. There was so much blood, I forget who won.

Yeah, well my primary concerns are getting something that works, behaves appropriately, and doesnt cause my MUD resources to shoot up to 70% or so for just a few areas.

Chances are that if I was using a coordinate system for my rooms each of those would work... to be truthful, I have more important things to try to optimize which would result in a larger gain based on the amount of time I put into it.

Alright, thanks for your input. And the reasons a mob would want to hunt down a player are very many... a player attacking the mob, for example, is a good reason, and surely a 'grudge' on the mobs part. Could be part of a quest, or someone might have hired out some assassins...

The summoning a creature to do something for you probably wouldnt work well on my MUD specifically but is a good idea and could still possibly be used [magic is still considered a rare, powerful thing. also, its based more so on my original view of what magic was before I was corrupted by other MUDs and dnd :) ].

Thanks again.

Chances are that if I was using a coordinate system for my rooms each of those would work... to be truthful, I have more important things to try to optimize which would result in a larger gain based on the amount of time I put into it.

They are all based on mathematical graphs, and have very little or nothing to do with coordinate systems. Hint: The traditional dikumud room system is a graph. You ought to actually read the flaming pages you said we wouldn't read.

Summoning the creature itself may not be what you are looking for, but if you can find code that allows a mud to have a creature that can be summoned to do what you want your mobiles to be able to do, then it may be worth looking into. Just allow all mobiles and players to do the same type of thing as that summoned mobile. I was just trying to point out practical examples of applications I have seen that utilized a tracking system.

The reason that I don't recommend most of the systems I have seen which utilize a grudge or memory system is that the AI didn't sound like what you were looking for. In most of them the mobile remembers the last character that attacked them. Then they randomly move around until they either find that individual, someone kills it, or someone else is placed in memory.

And the reasons a mob would want to hunt down a player are very many...

Hunting and tracking might be considered well separate from shortest paths. Depends on what you mean by it. That is a player or mob can certainly track each other without addressing the shortest paths problem at all.

The point of shortest paths is to get from point A to point B. That can be calculated either by assuming all paths are known or by using all known paths. By 'known' I mean the knowledge of the beast you're doing the search for. The former is quite easily implemented. The latter is not as easily implemented. The hunt implementation available as a Merc snippet assumes all paths are known, additionally assumes the location of the quarry is known, and additional is broken because it assumes Diku graphs are not cyclic.

(Comment added by Tyche on Wed Feb 2 16:35:49 2005)

I should amend the reason it's broken. It's not that it doesn't know the graphs are cyclic, it's that it doesn't remember the path it selected thus rendering it useless when in an area of a graph that is cyclic.

They are all based on mathematical graphs, and have very little or nothing to do with coordinate systems. Hint: The traditional dikumud room system is a graph. You ought to actually read the flaming pages you said we wouldn't read.

That's true, although based on my initial read over the A* stuff last night it seems that having a coordinate-based room system certainly helps you to build the path more efficiently, as you can make a better "guess" as to which direction to go.

I'm looking forward to trying to implement it this weekend in the MUD I'm tinkering on... Each room has a x,y coordinate so it should be ideal... I think. :)

I was reading through responses waiting for someone to correct his claims that not having a coordinate based system somehow hurt his ability to use A* searching...

Anyhow, your best bet is probably a modified, memory-limited A* search. Effectively, the lowest valued node is dropped when an upper limit of memory is reached. This prevents issues like insane swapping coming up, although the search is no longer guaranteed complete nor optimal.

Just for the record, you are really trying to do two seperate things here. First, getting from point A to point B is a simple pathfinding algorithm, nothing difficult involved. That was the "how do I get from Market Square to Castle Gate?" question. Your next _IS_ different; how do I get from point A to player A1 in as similar a manner as possible to how player A1 got to their current position (point B) from some point near point A. Following someone else's path, and finding your own path, are remarkably different issues. I haven't found a solution I particularly like for the first yet (although my creatures are using the coordinates to gain an advantage in walking in that direction, they lack a good knowledge base as yet so will walk stupid ways 'towards' the target sometimes), but the second can be mimic'd by some token players/monsters leave for some short while in every room they pass through; the search algorithm can locate these and it greatly reduces the search space dependent on how far apart tokens are dropped (if every 2 rooms, max number of searched nodes assuming 4 exits per room is 16).

Kelson

I'm happy to say that over the weekend I finally got my A* pathfinding code to work, and it works pretty well.

I've struggled with the concepts for a while, but it finally all began to make sense... woo!

I should say that my MUD uses a system where all rooms have a coordinate value, so it's easy to estimate which direction you should search in first.

Does anybody have any suggestions on how you would modify the A* to search for a particular room if your MUD doesn't assign coordinate values to rooms?

Not really an answer to your question, but I had some help with some pathfinding that is used in the wilderness. Allows mobs to track down their targets around sectors they cannot go through and can even wind through a maze (to a degree). It is mostly used to track down targets and determine if two points are linked between a road.

My codebase is available at www.rafermand.net/fear. The code is in caste.c it is called islinked.

If anyone finds it useful you are welcome to use it, just make sure to leave the comments in. It also used A* method.

(Comment added by xerves13 on Mon Feb 7 13:31:04 2005)

Could of sworn I posted that I did not write all of this code. There is some comments in for the original author. If you wish to use this code, that is all I ask to be perserved. Thanks.

--Josh

Does anybody have any suggestions on how you would modify the A* to search for a particular room if your MUD doesn't assign coordinate values to rooms?

h() = 0 in that case. Which makes Djikstra's more attractive.