Scent Rework

I don’t want to necro a 6-page thread, so I am starting fresh. The mechanics of scent have been discussed a fair bit in this thread: http://smf.cataclysmdda.com/index.php?topic=3811 and in this GitHub PR: https://github.com/CleverRaven/Cataclysm-DDA/pull/3818

As a summary, the goal of reworking scent is to make monster tracking less like a heat seeking missile and to slow down scent diffusion to support a sneaking mechanic. That means scent trails should be narrower and the cloud that surrounds the player should diffuse differently. Kevin summed up the roadmap for scent pretty well in his PR:

[ul][li]Making zombies (monsters with SMELLS, but not KEENNOSE) pause frequently when tracking by scent.[/li]
[li]Reduce sensitivity of scent ability when not KEENOSE[/li]
[li]Add upper threshold for scent intensity, if the area a monster is standing in is above it’s threshold, it can’t make a determination.[/li]
[li]Slow down scent diffusion.[/li][/ul]

He has rolled in #2 and #3. I have code locally that accomplishes #4 (and uses the discretized diffusion equation, which does better “conservation of mass” and should get rid of the wacky scents that occaisionally pop up). It’s about 50% slower than the current update_scent code, but I don’t notice a performance hit in my playtesting. I was going to do a PR, but… as I’ve been playing with the code a lot, I’ve noticed a couple of limitations that cannot be overcome in the current system.

[ol][li]scent only exists in a 40 x 40 window around the player. There is no way to extend this without exponentially increasing the amount of time it takes to compute scent.[/li]
[li]there is no good way to leave a “long lasting” scent trail. Partially because of the 40 x 40 window, but also because the player is the only source of scent. So dogs can’t smell the shirt you dropped, pick up your scent, and then follow the terrain that you walked on.[/li]
[li]adjusting diffusion affects everything, so to get a skinnier scent trail, you also get a proportionally smaller cloud around the player.[/li][/ol]

I have a proposal for changing how scent is represented that I think will be good, but I will need some help (or at least advice) in implementing it. Currently, scent is updated every turn as its own simulation, and this happens even if you are sleeping and there is absolutely no one near enough to smell you. I propose we instead keep track of the sources of scent that we leave (our tracks, but this could also include dropped items later), and then calculate the scent around a monster analytically if they are close enough to smell something. This would get rid of the 40 x 40 scent window, would allow us to make our footsteps leave traces of smell without them producing a big mushroom cloud, and boost game performance when there aren’t a bunch of nearby monsters smelling around for us. I think this also opens the door for adding wind. If implemented right, we could also account for z-levels (imagine zombies jumping out of apartment building windows because they smell you down below.) Also, you could set traps and drop used clothing on them to attract zombie dogs to their death. :slight_smile:

I have the mechanics of what I want to implement pretty well hashed out. Deciding how to account for walls and windows is the hardest thing I have left. I’m struggling with decisions on the implementation side, like: do I give scent sources their own class? Do I add them to the map class or keep them separate? Do I search for scent sources over a grid around the monster, or do I just pass the monster coordinates to some scent function defined in the class description? Those are the things I will need some help with. I’ll go into more detail in the next post.

Reserved.

A 50% increase in execution time is quite problematic, it’s already a major load, increasing it that much is bound to have impact on some systems.

All I was planning on doing for “narrower” scent trails was to simply slow down the simulation (by breaking up the scent cloud into independent zones and round-robbining through them on consecutive turns), this would result in a scent cloud not expanding as quickly, lower CPU usage, and a cloud that would reach the same size eventually. There might be enough lowered overhead there to extend the scentmap to the entire active map. Also for waiting we just need a simple mechanic to cut off the scent simulation after x turns of waiting/sleeping since it will have reached stasis already. Wind complicates this, but really not that much, we’d just restart the diffusion simulation periodically when the wind condition changes.
If you want items or locations to generate scent, it’s as simple as sticking them on a list and adding their scent to the scentmap before running the diffusion simulation, it shouldn’t impact performance at all. Could either tie it to items, or make a “scent source” object that lives on the map, potentially one that decays with time itself.

I’d like to hear about the mechanics in more detail. It seems to me instead of one pass over the map to perform diffusion, you’d end up with lots of scans across large portions of the map to look up all the scent sources, or at best MxS with M being number of monsters and S being number of scent sources. If the player drops a long-lived scent source with every step, that number can get quite high, especially with weird tactical manuverings, and we support up to thousands of zombies on the map at once, so that’s a LOT of scans.

I haven’t had a good chance to post ideas into this thread on doing analytical calculations. I’ll get around to it eventually. In the mean time, I made a PR that I think improves the current system. It’s here: Better, Faster Scent by phaethonfire · Pull Request #4591 · CleverRaven/Cataclysm-DDA · GitHub

I think you’re right, though I’m not sure that scent is the biggest culprit for slowing down the game. On my system it uses ~0.4 seconds over 100 turns. I spent a while thinking about the implementation, made some tweaks, and ended up with a speed improvement while keeping the better physics. See what you think.

I saw you added the “stop updating when the player has been still a long time” feature, which is great. As for slowing down the simulation, doing it by quadrant might cause some weird artifacts. If we really need more performance, it should be doable to diffuse in the x direction on even turns and the y direction on odd turns. The scent cloud would still be a little skewed half the time, but it would be fully corrected the next turn since the diffusion can be decomposed into x and y planes and solved sequentially. If the diffusion constant is added, we should be able to control diffusion directly.

Yeah, it may or may not be good for performance, but it wouldn’t be as bad as MxS. For one, we don’t have to look at scent sources that aren’t near a given monster. We’ll see if I ever get around to trying to make it work. If it worked, it would allow some added game features, but with so much being added to the game, long-term scent tracking doesn’t seem very important. Just not much incentive to do all that is needed to change it.

By the way, how big is the “entire active map”?

I thought I had some ways to handle the artifacts you mentioned from breaking up scent updating by quadrants or by doing a sweep around the player (think radar or sonar visualization), but none of them worked out. I think what we have now is superior anyway.
The whole map is currently 121x121 squares, and with merged z-levels will be 121x121x21 squares, meaning there may need to be a third sweep for the scent code to handle vertical diffusion.