How should I use Monte Carlo method to simulate some police cars that keep patroling in a tile based map?

Question

I have a tile map (isometric) and I have some police cars that they patrol all the time on the map, there is some building and other cars in map too so they are considered as constraints in my shortest path algorithm (below).

I use to randomly select some target for each police car and use A* algorithm to find the path to the randomly selected destination tile and this cycles over and over. because cars should move all the time! (except those that gamer should control)

The problem is police cars routes are correlated and they do not just traverse the area randomly, for instance, they do not usually cover a same area or they do not repeat their own route so my implementation based on some random destination point wasn’t a good idea and the result was not satisfying. Take a look at the following picture, it shows how randomly selecting the destinations worked for me, obviously, it is a dumb patroling for sure, even a cockroache could do better!

Suddenly, I remembered Monte Carlo Method and I thought it would solve my problem, because it exactly does what I wanted to do, However may be I should use Zobrist Hashing since it is tile base in nature. Does anyone has any idea how should I use this kind of methods?

Question in Brief :

How can I use Zobrist Hashing or Monte Carlo method to set destinations points for my patroling car (like police car)? If anyone knows another way to implement a patrolling method, he/she is very welcome to post an answer, I am not sure if Zobrist Hashing is the best and worth to implement.

---First Edit (added following paragraph) :

I need to distribute the cars and their destination points in a homogeneous manner. Every kind of solution that get me close to a good pattern could be my answer, of course there is a lot of methods to do so, but I dont have any clue.

Answer 1

As a former police officer I can offer some insight into how it really works, which might help refine your process.

Divide your area up into grids and assign a car to patrol in that area, the areas may overlap a bit but the aim is to ensure a geographic spread. This reduces the problem that Alex's graphic can show - that you get two cars essentially following each other around. You often see this problem in Sim City type games (for some reason garbage trucks spring to mind).

Within that area you can have a mix of total randomness. You won't nescessarily visit every street as a police officer. You aren't even necessarily looking for efficiency with A*. What you could do is identify "hot" areas of the graph of streets and emphasise travelling over them. If you weighted streets for crime then something like a Kruskal's algorithm could be used.

If you want to add a bit more realism then occasionally generate "calls" which then would use A* to travel to a location for the car. You could even grade the calls to occasionally pull neighbouring cars out of their areas for serious ones, and then have them head back once the call is completed. Add in a "busy" state for cars, perhaps with a distance / severity ratio to see if they drop what they are doing to answer a call.

Depends how far you want to take things. But in general you're not wanting true randomness, it won't look random.

Answer 2

How would a real police patrol a neighbourhood?

Presumably they would go to the "hottest" spots? Or the closest spot that they did not visited for some time?

I've tried something with a "dirt map" because criminals do dirty business. Each frame, each spot get "dirtier".

Currently in my test the patrol car goes to an intersection that has the most "dirt" combined with the shortest distance. Once the destination selected, it flags the destination so that no one else go there (you don't want all the police cars go patrol at the same sport at the same time).

Is this way to go appropriate? Maybe.

But maybe not. Maybe "theoretically" it is a good approach, but "realistic" games would be boring so it might not answer well to the "fun" need.

So what I suggest would be to clearly decouple your "find where to go" from your "go there" algorithm so that you could experiment easily.

From what I understand, the Monte Carlo algorithm is more related to statistical stuff, and your need has nothing much to do with statistics. It has too be based on a need.