Algorithm for finding nearest animal on board

Question

So I am writing a simulation of a rabbits and wolfs - there is a set amount of wolves and rabbits in the beginning, rabbits run away from wolfs and wolfs chase rabbits, when they meet in the same block rabbit gets killed and simulation ends when there are no rabbits left. I wrote most of the code, however I don't know how to make it so that rabbit run away from wolves and wolves chase rabbits. I have to first write an algorithm that finds nearest animal and then calculate the best move (that's an easy part).

Animals can move up, down and cross in 1 thread cycle, and if there are for example 2 wolves that are away by 2 moves then I have to randomize the one I run away from (same goes for wolves and chasing rabbits).

My first approach is that I somehow (possibly recursively?) search the array starting from my given animal and then going in circles around it like that:

So first iteration it found no wolves, second it found 2, so it saves both of their coordinates, ends it work and passes it to the function that randomizes a choice. Now, I think it would be the best idea but I don't know how to implement it :( I tried for few hours but I gave up cause I didn't reach anywhere.

Second approach, pretty naive, would be to find all wolves on the board and then for each calculate amount of moves needed to get to the rabbit and just save the ones with smallest amount. That I can code, but I think it would be really inefficent for bigger boards.

Answer 1

Rabbit should look at all wolfs to live longer. If he would just run away from closest one - it may be a big mistake.

In this case he would live really long if wolf prefer to go "UP" instead of "RIGHT", or "RIGHT" instead of "DOWN" (clockwise priority). Also, rabbit may become immortal if there is just several non-randomized wolfs)

The simplest logic I can suggest is to check all wolfs on board and choose 5 closest, sort them by manhattan ditances (dx+dy), and let it be D1,D2,D3,D4,D5.

So, let "D - how dangerous it is to go in some cell". Compute

D = D1*A + D2*B + D3*C + D4*D + D5*E

A > B > C > D > E

for all 4 cells adjacent to current rabbit cell. And choose the cell with minimal value (you need to find A,B,C,D,E by experiments). I think you can also make some upper bound for D1,D2,D3,D4,D5. For example, the wolf which is D4 or D5 is really far - he should not gain any influence, so just make D4 = D5 = 0.

Of course, this logic will fail in such cases

But I don't think there is something we can do at all) so it's not a case we're trying to optimize

Answer 2

This is a Closest pair of points problem

Here is an implementation: http://algs4.cs.princeton.edu/99hull/ClosestPair.java.html

Your objects can only move vertically or horizontally, so you need to replace the distance with x+y.

Answer 3

If the number of objects on the board is much less than the board itself (say, the board can be up to 1000x1000 but there are at most 10,000 wolves), a practical approach would be to store the coordinates of each object separately. Then, you can inspect the list of wolves without having to find them on the board every time.

To maintain both representations, one will need references in both directions: each board cell has a pointer to the object contained in it (a list of pointers if there can be several of them), and each object contains the coordinates of its cell. There is also a separate list (or array) containing (pointers to) all existing objects, or maybe two separate lists for wolves and rabbits, depending on what you need to iterate frequently.