Scent based pathfinding using C# in games

Was wondering if anyone has knowledge on implementing pathfinding, b开发者_开发技巧ut using scent. The stronger the scent in the nodes surrounding, is the way the 'enemy' moves towards.

Thanks

---

Yes, I did my university final project on the subject.

One of the applications of this idea is for finding the shortest path. The idea is that the 'scent', as you put it, will decay over time. But the shortest path between two points will have the strongest scent.

Have a look at this paper.

What did you want to know exactly??

---

Not quite clear what the question is in particular - but this just seems like another way of describing the Ant colony optimization problem:

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

---

Well, think about it for a minute.

My idea would to divide the game field into sections of 32x32 (or whatever size your character is). Then run some checks every x seconds (so if they stay still the tiles around them will have more 'scent') to figure out how strong a scent is on any given tile. Some examples might be: 1) If you cross over the tile, add 3; 2) if you crossed over an adjacent tile, add 1.

Then add things like degradation over time, reduce every tile by 1 every x seconds until it hits zero.

The last thing you will need to worry about is using AI to track this path. I would recommend just putting the AI somewhere, and telling it to find a node with a scent, then goto an adjacent node with a higher/equal value scent. Also worry about crossing off paths taken. If the player goes up a path, then back down it another direction, make sure the AI does always just take the looped back path.
The last thing to look at with the AI would be to add a bit of error. Make the AI take the wrong path every once in a while. Or lose the trail a little more easily.

Those are the key points, I'm sure you can come up with some more, with some more brainstorming.

---

Every game update (or some other, less frequent time frame), increase the scent value of nodes near to where the target objects (red blobs) are.

Decrease all node scent values by some fall-off amount to zero.

In the yellow blob's think/move function get available nodes to move to. Move towards the node with the highest scent value.

Depending on the number of nodes the 'decrease all node scent values' could do with optomisation, e.g. maybe maintaining a a list of non-zero nodes to be decreased.

---

I see a big contradiction between scent model and pathfinding. For a hunter in the nature finding the path by scent means finding exactly the path used by the followed subject. And in games pathfinding means finding the fastest path between two points. It is not the same. 1. While modelling the scent you will count the scent concentration in the point as the SUM of the surrounding concentrations multiplied by different factors. And searching for the fastest path from the point means taking the MINIMUM of the times counted for surrounding points, multiplied by the different parametres. 2. Counting the scent you should use recursive model - scent goes in all directions, including backward. In the case of the pathfinding, if you have found the shortest paths for points surrounding the target, they won't change. 3 Level of scent can rise and fall. In pathfinding, while searching for minimum, the result can never rise.

So, the scent model is really much more complicated than your target. Of course, what I have said, is true only for the standard situation and you can have something very special...