CODEWITHSUNDEEP
javaandroidalgorithmartificial-intelligence
UDKOX
UDKOX

Reputation: 737

Android path seeking algorithm

Context

I am trying to develop a simple 2D game where some "zombies" are going to chase me.

My idea to calculate the paths was the following (X = path not usable):

[4] [4] [X] [1] [1] [2] [3] [4] [5]
[3] [X] [X] [0] [1] [X] [X] [X] [5]
[3] [2] [1] [1] [1] [X] [3] [4] [5]
[3] [2] [2] [2] [2] [2] [3] [4] [5]

Starting from 0, give the positions arround it 1 value, to those close to 1, give 2 value, etc. This way I just need to search for an lower index to know the quickest way to reach 0.

Questions

(1) I don't know if this algorithm has a name so I could not really find information about it.

(2) The most optimal solution/algorithm/flow to calculate this

(3) In my mobile, the game screen has 1700 x 1440 resolution, so my code takes 15 seconds. I crated a final value to scale everything down and lower the matrix size, however, stil takes a lot, literally unplayable.

(4) Are there other needs ? Maybe adding threads ? I don't know if would that work though ...

My code (debug code deleted)

Code

private void expandAllFrom(int x, int y){ // x and y already scalled down
    nodes = new ArrayList<Point>(); // "nodes" is a global variable //
    nodes.add(new Point(x, y));

    while ( nodes.size() > 0 ){
        Point p = nodes.remove(0);
        expand(p.x, p.y);
    }
}

private void expand(int x, int y){
    int limXMin = x - 1, limXMax = x + 1, limYMin = y - 1, limYMax = y + 1;
    int value = map[x][y];

    // Check limits of screen
    if ( limXMin < 0 ) limXMin = 0;
    if ( limXMax > SCREEN_X_DIV - 1) limXMax = SCREEN_X_DIV - 1;

    if ( limYMin < 0 ) limYMin = 0;
    if ( limYMax > SCREEN_Y_DIV - 1) limYMax = SCREEN_Y_DIV - 1;

    for (int i = limXMin; i <= limXMax; i++){
        for (int j = limYMin; j <= limYMax; j++){
            if ( map[i][j] == 0 ) {
                if ( i != x || j != y ){
                    nodes.add(new Point(i, j));
                    map[i][j] = value + 1;
                }
            }
        }
    }
}

Explanation

I use a FIFO list. I add the nodes in there, for example, the flow would be something like: 

(1) Add 0 position to expand node list.
(2) Expand 0 by setting 1 values arround it. Then add them to expand node list.
(2) Expand 1 by setting 2 values arround it. Then add them to expand node list.
(...)
(X) Expand 2 by setting 3 values arround it. Then add them to expand node list.
(Y) Expand 3 by setting 4 values arround it. Then add them to expand node list.
(...)

Upvotes: 2

Views: 436

Answers (2)

BKE
BKE

Reputation: 573

As mentioned, what you do is called breadth first search, which is a special case of Dijkstra's algorithm. Well done for finding it out for yourself!

The problem is, that the time complexity of BFS is O(V+E), where V is the number of nodes, E is the number of edges. In your case, it will be in the order of the size of the map, depending on the sparsity of the map (that is, how many X-es there are). That is in any case in the order of millions for a map of size 1700x1440.

If the number of zombies is not too big, it would be much faster to calculate the shortest path for each zombie one by one (you could still share and re-use the expanded nodes between the zombies), using variations of BFS with heuristics. For example, jump point search is optimized for uniform cost mazes (jump point search is a special case of the A-star algorithm).

The idea there is to take a start point (a zombie's position) and an end point (the player's position), and to calculate the shortest path between them, expand the nodes which are closer to the destination first. Closer here means that the approximated distance to the endpoint is less. The distance to the reached nodes is known, and A star will choose the node where the sum of the distance from the start to the node, plus the approximated distance from the node to the end is the smallest. Since you allow diagonal moves, the distance approximation can not be the Manhattan distance, nor Eucledian distance, as the approximation has to be a lower bound to the real distance. You could take eg. max(│x-x'│, │y-y'│). Jump point search improves this further by taking advantage of the maze structure of the map, to exclude further nodes.

This site animates several such algorithms so you can get a feel how these work.

The nice thing about this approach is that you would not search through the whole map, only a small fraction of it which lies between the zombie and the player. This could already be orders of magnitude faster than any full scale BFS algorithm. To show how dramatic the speedup can be, have a look at the following images. Only the marked nodes are explored by the search:

A star search jump point search

Another advantage is, that you could compromise between running time and the 'cleverness' of the zombies. All you have to do is not run such an algorithm all the way to the end point. You can stop after a pre-defined number of steps and get just an approximation for the beginning of the path (by looking at the shortest path between the start point and the most promising node to expand next). So depending on how much time you have for the calculation, you could have optimal or less optimal zombies.

Upvotes: 1

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

This is just breadth-first search (BFS), used to find the single-source shortest path. The numbers you want to calculate correspond exactly to the level in which each grid cell is located. The nice thing is that with a proper implementation of BFS, you don't need the numbers. Just start the BFS procedure at the player's location, then let each zombie step towards the parent-pointer of the cell they are currently in.

Upvotes: 2

Related Questions