Learning to be Imperfect an alternative to Dijkstra pathing that stinks.

[King Ink]

I think that the Dijkstra is a perfect method for finding the shortest paths through even the knottiest mazes.
It is gorgeous it is beautiful it is quick.
 But in my opinion it does not reflect how real organisms solve pathing issues.
anything produced by evolution can not be that efficient can not have such perfect knowledge of its environment.
so I came up with an alternative that brings joy to my nerdy little heart.   
Pathing by Smell.
works much like Dijkstra the goal releases a smell that smell diffuses wafts throughout the maze in game time taking turns being blocked by wall and whatnot.
critters that like the stink move to adjacent squares that have more of it then the square they are on.
fleeing creatures move to squares of less stink.
there you go.   
I wrote a game to show how it works
Stink Warrior

[Quendus]

I wrote KleinRL with a similar mechanic. It interacted quite badly with the speed system; when you're slow, monsters path perfectly to your location, and when you're fast they can barely find you because they search for where you were 2 - 10 turns ago. I'll try Stink Warrior and see what it's like.

One possible way to make scent pathfinding more fallible is to add random noise to creatures' perception of smell values. The distance at which scent strength is equal amplitude of the noise is approximately the point where creatures can't find you reliably. I did this in Mutant Aliens/Aristocrats, but there they use sight/sound/telepathy to find your location and that interferes with it, so I can't tell how well it works. It takes a bit of experimentation to match the smell decay rate to the noise amplitude and number of scent processing iterations per turn.

Edit: 2 and 8 are reversed in the controls

[King Ink]

I wrote KleinRL with a similar mechanic. It interacted quite badly with the speed system; when you're slow, monsters path perfectly to your location, and when you're fast they can barely find you because they search for where you were 2 - 10 turns ago. I'll try Stink Warrior and see what it's like.

One possible way to make scent pathfinding more fallible is to add random noise to creatures' perception of smell values. The distance at which scent strength is equal amplitude of the noise is approximately the point where creatures can't find you reliably. I did this in Mutant Aliens/Aristocrats, but there they use sight/sound/telepathy to find your location and that interferes with it, so I can't tell how well it works. It takes a bit of experimentation to match the smell decay rate to the noise amplitude and number of scent processing iterations per turn.

Edit: 2 and 8 are reversed in the controls

are they? crap I wrote it on a laptop.
l

[guest509]

I love it. Interesting behavior is fun. I've never gotten further than 'walk this way for a bit' and then 'walk that way for a bit' and 'hit wall, change directions' and then 'see player, turn his way', etc...

I never thought coding movement would be fun, but it is.

[King Ink]

I fixed the 8 and 2 swap.
and added a much needed 't' to the word daugher.
that key sticks on my computer.

but no further support 

[wire_hall_medic]

I find it really pretty.  Is the increasing stench a function of depth, turns, or am I just wandering too close to corpses? 

Also, I like all the fluff; status conditions, inventory, etc.

[King Ink]

thank you.
time, eating rotten food, vomiting from eating rotten food and crapping yourself.
I did not test for difficulty at all I assume you just do a little dancing to get rid of rats and find stairs.
 

[Kevin Granade]

We were discussing this on the cataclysm forums just recently, most enemies have a scent ability that works via the same diffusion and hill-climbing (or descending) mechanic, in addition to sight and hearing.  In our case it's largely a stand-in for our AI being nearly nonexistent, monsters remember only the most recently heard noise and the most recent location where an enemy was seen.

Scent is particularly critical for when the player ducks through a door and barricades it, because otherwise the zombies would quickly forget where they are and give up bashing on the doors and windows.  Also it tends to dominate at night or in other low-light situations.  The scent is "perfect" in its hill-climbing, but I recently added an upper threshold such that when the scent level is above it, the scent ability stops working, so enemies can't unerringly close in on the player.  It gets them within about 4 tiles of the player, but if they can't see or hear the player, they just start stumbling around at random.

Noise on the other hand has "noise" added to the reported location, based on distance, volume and perception of the hearer.  This includes players, we display question marks to indicate noises heard in areas the player can't see.

[guest509]

That's some design gold right there Kevin. The illusion of sophisticated AI. I really like that.

[Gr3yling]

Noise on the other hand has "noise" added to the reported location, based on distance, volume and perception of the hearer.  This includes players, we display question marks to indicate noises heard in areas the player can't see.

I really wanted to use that question mark idea, but I was afraid that it would be unclear to the player what they meant.  It's good to see that it is possible to implement it successfully.

[akeley]

Powder uses similar "question mark" mechanic, I thought it worked really well.

[Kevin Granade]

Of topic, oops:
A refinement I'd like to make to the noise question marks is to make them persistent until the player moves, and allow them to be examined, yielding a description of the sound.  Some might be a generic "scrape" or "thud", some might be a more telling "moan" or "boom".