iOS Maths problem... calculating shortest distance to exit based on a varying path

[MythicFrost]

Hey there,

I'm building a simple 2D game. The grid is a 2D int array which is populated with 0's. The 0 means a unit can move to that tile and any other number means you can't, let's call it a 1 though. The player places structures which set the value in that row and column to 1 which means a unit can't move there.

I'm wanting to calculate the fastest way for a unit to move through this kind of grid. The grid is 10x15 but let's say it's 5x5:

(0/1/ 2/ 3/ 4 column)
0, 0, 0, 0, 0 (row 0)
0, 1, 1, 1, 0 (row 1)
0, 1, 0, 0, 5 (row 2)
0, 1, 0, 1, 0 (row 3)
0, 0, 0, 1, 0 (row 4)

The unit will start where the 5 is. The fastest route would be to go up and left, and the longest but most obvious would be to go left, down and left. How would I go about navigating my 2D array and finding the (first) quickest path?

This is something I've never dealt with before so I'm in new territory here. I've spent a couple of hours trying to figure this out and so far I've thought of this:

Have a "pathsArray" and in some kind of loop add every possible combination path which makes it to the end (i.e, isn't blocked) to an array and then add that array to pathsArray.

Then, all I have to do is choose from the arrays in pathsArray and pick the shortest one. This is my code so far:

    NSMutableArray *pathsArray = [[NSMutableArray alloc] init]; //add each array with the paths in it to this list and then look for the one with the fewest movements
    
    for (int i = colMax; i > 0; i--) {
        for (int k = rowMax; k > 0; k--) {
            //start searching from the very bottom right of the grid, going up
        }
    }

I'm not exactly sure where to start. Is two for loops the correct way to go about this? Or should I use a while loop? Oi! This is far above my head. Would appreciate ANY input! Thanks.

 

[jiminaus]

Welcome to artificial intelligence.

 

[MythicFrost]

Welcome to artificial intelligence.

Thanks... aaaaah. I'm reading this at the moment: http://en.wikipedia.org/wiki/A*_search_algorithm

 

[MythicFrost]

I've been working against this code I found:

cst <- cost matrix
q <- empty queue
q.insert(xi, yi)
while q is not empty
    cur_x, cur_y = q.pop()

    if cur_x == xf and cur_y == yf
        return cst(cur_x, cur_y)

    for all neighbour positions (xn, yn) of (cur_x, cur_y)
        if (xn, yn) is valid and (xn, yn) has not been visited
           q.insert(xn, yn)
           mark (xn, yn) as visited with cost cst(cur_x, cur_y) + 1


return 'no path'

I have this so far:

- (int)findPathFromRow {
    
    NSMutableArray *q = [[NSMutableArray alloc] init];   
    int checkingMap[10][15]; //I put this in place of "cost matrix" although I think I've got the wrong idea here... [10][15] should be an array of paths taken not an int right?
    
    for (int i = 0; i < 10; i++) {
        for (int k = 0; k < 15; k++) {
            if (i == 0 || i == 9) {
                checkingMap[i][k] = 1;
            } else {
                checkingMap[i][k] = 0;
            }
        }
    }

    [q insertObject:[NSString stringWithFormat:@"%i %i", colMax-1, rowMax-2] atIndex:0];
    
    while (q.count > 0) {
        NSString *data = [q objectAtIndex:0];
        [q removeObjectAtIndex:0];       
        NSArray *split = [data componentsSeparatedByString:@" "];
        
        NSString *xValue = [split objectAtIndex:1];
        NSString *yValue = [split objectAtIndex:0];
       
        int cur_x = [xValue intValue];
        int cur_y = [yValue intValue];
       
        if (cur_x == 0) {
            return checkingMap[cur_x][cur_y];
        }

        int xVal = cur_x-1; //left
        int yVal = cur_y;
    
        if ([self canMoveToTileAtRow:xVal atColumn:yVal] && checkingMap[xVal][yVal] == 0) { // == 0 not visited
            [q insertObject:[NSString stringWithFormat:@"%i %i", xVal, yVal] atIndex:0];
            checkingMap[xVal][yVal] += 1;
        }
        
        xVal = cur_x+1; //right
        yVal = cur_y;
        
        if (xVal < colMax-1) {
            if ([self canMoveToTileAtRow:xVal atColumn:yVal] && checkingMap[xVal][yVal] == 0) { // == 0 not visited
                [q insertObject:[NSString stringWithFormat:@"%i %i", xVal, yVal] atIndex:0];
                checkingMap[xVal][yVal] += 1;
            }
        }
       
        xVal = cur_x; //up
        yVal = cur_y-1;
      
        if ([self canMoveToTileAtRow:xVal atColumn:yVal] && checkingMap[xVal][yVal] == 0) { // == 0 not visited
            [q insertObject:[NSString stringWithFormat:@"%i %i", xVal, yVal] atIndex:0];
            checkingMap[xVal][yVal] += 1;
        }
        
        xVal = cur_x; //down
        yVal = cur_y+1;

        if (yVal < rowMax-1) {
            if ([self canMoveToTileAtRow:xVal atColumn:yVal] && checkingMap[xVal][yVal] == 0) { // == 0 not visited
                [q insertObject:[NSString stringWithFormat:@"%i %i", xVal, yVal] atIndex:0];
                checkingMap[xVal][yVal] += 1;
            }
        }
    }
    return -1;
}

How's this look? Does anyone know? I think I'm on the right path...

 

[chown33]

You haven't posted enough code. You're missing an important method, and the @interface hedaer that declares ivars. So no one can compile and run it to see what happens.

Write a test program. Then give it some test data. Then see if it produces a correct result.

Personally, I like to build tests as Cocoa command-line tools, runnable from Terminal. If they read data from a file named as a command-line arg, so much the better. This is one reason for learning how to write non-GUI programs that do classic scanf() and printf().

 

[MythicFrost]

You haven't posted enough code. You're missing an important method, and the @interface hedaer that declares ivars. So no one can compile and run it to see what happens.

Write a test program. Then give it some test data. Then see if it produces a correct result.

Personally, I like to build tests as Cocoa command-line tools, runnable from Terminal. If they read data from a file named as a command-line arg, so much the better. This is one reason for learning how to write non-GUI programs that do classic scanf() and printf().

Ah, right. Okay, I've worked on it a while after this and have it working however the functionality isn't desired. Whilst it finishes as soon as it reaches the left side, it doesn't provide the quickest path. (I.E, there are still unnecessary movements made.)

So, I moved on to working on a different algorithm (Dijkstra's algorithm) and I'm trying to apply it to my code which has proved difficult since I don't entirely understand the algorithm and specific terms. The algorithm is here: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

The example (gif) image it has is this which is exactly what I'm trying to achieve:

The code I'm using right now is a mess compared to the original because I don't know either the equiv. in Objective C, or it isn't possible, and thus I'm using a workaround which is terrible, for example:

(I should note, I'm not looking for help getting this code working rather how to clean it up and do it properly, as described in more detail toward the bottom of the post.)

This is pseudocode from the wiki link above:

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:            // Initializations
 3          dist[v] := infinity ;              // Unknown distance function from source to v
 4          previous[v] := undefined ;         // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                    // Distance from source to source
 7      Q := the set of all nodes in Graph ;
        // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                  // The main loop
 9          u := vertex in Q with smallest distance in dist[] ;
10          if dist[u] = infinity:
11              break ;                        // all remaining vertices are inaccessible from source
12          end if ;
13          remove u from Q ;
14          for each neighbor v of u:          // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:              // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19                  decrease-key v in Q;       // Reorder v in the Queue
20              end if ;
21          end for ;
22      end while ;
23      return dist[] ;
24  end Dijkstra.

This is my code: (it compiles, but it doesn't do anything... I wouldn't expect it to either.)

- (NSMutableDictionary *)findPath {
    
    int intGraph[10][15] = { //map
        {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
        {0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 0},
        {0, 0, 5, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0},
        {0, 0, 5, 5, 5, 0, 5, 0, 5, 0, 5, 0, 0, 5, 0},
        {0, 5, 0, 0, 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 0},
        {0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 5, 0, 0, 5, 0},
        {0, 5, 0, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 0},
        {0, 0, 0, 0, 5, 0, 5, 0, 5, 0, 0, 0, 5, 0, 0},
        {0, 5, 0, 0, 5, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0},
        {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
        
    };
    
    int colMax = 15;
    int rowMax = 10;
    
    int sX = colMax-1; //sourceX
    int sY = rowMax-1; //sourceY
    
    NSMutableDictionary *dist = [[NSMutableDictionary alloc] init];
    NSMutableDictionary *previous = [[NSMutableDictionary alloc] init];
    NSMutableArray *q = [[NSMutableArray alloc] init];
    
    for (int i = 0; i < 10; i++) {
        for (int k = 0; k < 15; k++) {
            NSString *key = [NSString stringWithFormat:@"%i %i", i, k];
            
            [dist setObject:[NSString stringWithFormat:@"%f", INFINITY] forKey:key];
            [previous setObject:[NSString stringWithFormat:@"%i", -1] forKey:key];
            
            [q addObject:key];
        }
    }
    
    [dist setObject:@"0" forKey:[NSString stringWithFormat:@"%i %i", sY, sX]];
    
    while (q.count > 0) {
        
        //find vertex in Q with smallest distance in dist[]
        NSString *smallestVertex = [q objectAtIndex:0];
        for (int i = 1; i < q.count; i++) {
            int dist1 = (int)[dist objectForKey:smallestVertex];
            int dist2 = (int)[dist objectForKey:[q objectAtIndex:i]];
            
            if (dist2 < dist1) {
                smallestVertex = [q objectAtIndex:i];
            }
        }
        
        NSString *u = smallestVertex;
        
        int uValue = (int)[dist objectForKey:u];
        
        if (uValue == INFINITY) {
            NSLog(@"break");
            break;
        }
        
        [q removeObject:u];
        
        NSMutableArray *neighbors = [[NSMutableArray alloc] init];
        
        //get neighbours of the vertex smallestVertex / u
        NSArray *split = [smallestVertex componentsSeparatedByString:@" "];
        
        NSString *row = [split objectAtIndex:0];
        NSString *col = [split objectAtIndex:1];
        
        NSString *keyLeft = [NSString stringWithFormat:@"%i %i", [row intValue], [col intValue]-1];
        NSString *keyRight = [NSString stringWithFormat:@"%i %i", [row intValue], [col intValue]+1];
        NSString *keyUp = [NSString stringWithFormat:@"%i %i", [row intValue]-1, [col intValue]];
        NSString *keyDown = [NSString stringWithFormat:@"%i %i", [row intValue]+1, [col intValue]];
        
        //add to array, loop through (neighbours) and check they're in q
        
        NSArray *keyGroup = [[NSArray alloc] initWithObjects:keyLeft, keyRight, keyUp, keyDown, nil];
        
        for (int i = 0; i < keyGroup.count; i++) {
            for (int k =0; k < q.count; k++) {
                if ([[keyGroup objectAtIndex:i] isEqualToString:[q objectAtIndex:k]]) {
                    [neighbors addObject:[keyGroup objectAtIndex:i]];
                    //break; //exit from for loop
                }
            }
        }
        
        //loop through neighbours
        
        for (int i = 0; i < neighbors.count; i++) {
            //get the
            NSString *v = [neighbors objectAtIndex:i];
            int vDist = [[dist objectForKey:v] intValue];
            int uDist = [[dist objectForKey:u] intValue];
            
            int dist_between = uDist-vDist; //distance between (u, v)
            
            NSString *alt = [dist objectForKey:u];
            int altValue = [alt intValue];
            altValue += dist_between;
            alt = [NSString stringWithFormat:@"%i", altValue];
            //^ set alt to dist[u] then add dist_between and then put it back into a string
            
            if (altValue < vDist) { //Relax (u, v, a)
                [dist setObject:v forKey:alt];
                [previous setObject:v forKey:u];
                
                //decrease-key v in Q;
                int index = [q indexOfObject:v];
                [q removeObject:v];
                [q insertObject:v atIndex:index+1];
            }
        }
    }
    return diet;
}

I'm hoping you might be able to point out some of my seemingly obvious mistakes so I can at least get on the right path. For example, I don't know how to do a for each statement in Objective C so I used two for loops and I don't know how to use dimensions like with dist[2,1] so I'm using an NSMutableDictionary so I can store the data (as a string) and retrieve it with a vertex (e.g., 2,1, 3,5 8,14).

This part of my code:

    for (int i = 0; i < 10; i++) {
        for (int k = 0; k < 15; k++) {
            NSString *key = [NSString stringWithFormat:@"%i %i", i, k];
            
            [dist setObject:[NSString stringWithFormat:@"%f", INFINITY] forKey:key];
            [previous setObject:[NSString stringWithFormat:@"%i", -1] forKey:key];
        }
    }

Is an attempt to copy this:

2      for each vertex v in Graph:            // Initializations
 3          dist[v] := infinity ;              // Unknown distance function from source to v
 4          previous[v] := undefined ;         // Previous node in optimal path from source
 5      end for ;

To clarify above, I'm not looking for anyone to help me get this code "working" rather to help me clean it up first, I'm sure I'm doing plenty of things the wrong way and I could use a push in the right direction.

I've tried to match it line for line but I often required more code since I was using NSMutableDictionary. To note, I've tried four or five different ways of writing this code out before I ever got to using NSMutableDictionaries, I'm just stumbling around in the dark here looking for something that works.

I'd appreciate any input.

EDIT: These are some questions I'm looking for the answers to that will help me clean up my code:

1) The graph, is it my 2D int array?
2) What is a vertex? Is it coordinates like 2,1 and 5,7, etc.
3) What are nodes? These are vertices, yes?
4) When it says q should be the set of all nodes in graph, does that mean I add all the possibly vertices in my graph to q which is a one dimensional array?
5) How is it calculating the distance between u and v if it's a vertice
6) Is this written for a 1D graph? Is that why it only has one dimension, or is it a placeholder?
7) Assuming a vertex is a coordinate (which is what I think it is), I'm unsure how to use it in an array like dist[v]. My first thought is dist[x][y] but I tried that and decided to give up and try another solution (using NSMutableDictionary) considering I'm stumbling around in the dark here.

 

[chown33]

Your first big mistake is in trying to translate word for word or line for line. For example, expecting an actual all-encompassing "for .. each", or not understanding what array[x,y] means.

You need to understand the meaning of the code. What it communicates overall, not the specific words it uses. There is no "for each neighbor" statement in C, Objective-C, or any other language I know of. If you know what the concept "neighbor" means, then you know how to code it. If you don't know what "neighbor" means, then you'll get lost trying to find a "for each neighbor" looping structure.

So what do you think "neighbor" means, in the context of the algorithm? Does it mean "immediately adjacent to, either in the same row or column", or maybe even including diagonal row and column. If you don't understand the basic geometry of the representation, you can't possibly understand a solution that uses geometry.


Your second mistake is not recognizing the row,column notation of the algorithm, and relating that to C. In C, a 2D array of rows and columns is addressed by array[row][column]. This is equivalent to array[row,column] in the algorithm description. The latter is common in other languages, just not in C or C-like languages.

Furthermore, Objective-C NSArrays only have one dimension. There's no such thing as row/column addressing of NSArrays. You can, however declare an array of arrays. Each object in the "array of rows" is another array: the columns for that row.

You can also make a single NSArray with pseudo-row/column addressing. For a row and column index (r,c), multiply r by the total number of columns, then add c. The resulting index identifies a single array location: i = r * numCols + c.


If that's all too confusing, then you're in way over your head, and you need to go back and review fundamentals.

For starters, learn about C arrays and row/column addressing. Then figure out what "neighbor" means in a row/column array, and think about how you'd actually implement that: both the indexing and the iteration of all neighbors. You should be able to solve it using plain C, with no NSArrays at all. And even using Objective-C, none of this involves NSDictionary classes, nor format strings.

 

[sammich]

This looks vaguely familiar

I took an AI class in the first half of last year on nearly the exact same problem. We had to program several types of 'searching' algorithm (BFS, DFS, A*, Greey, Hill) to get a 'robot' to the target point in a grid with our choice of heuristic. It was one of my more fun assignments. I wrote it in C++.

I won't post the assignment scheme, I can PM it if you are curious.

In a simple grid array, you can stick with just A*. It's a relatively simple path searching algorithm but it works if you choose the right heuristic to label each cell in the grid.

 

[MythicFrost]

Your first big mistake is in trying to translate word for word or line for line. For example, expecting an actual all-encompassing "for .. each", or not understanding what array[x,y] means.

You need to understand the meaning of the code. What it communicates overall, not the specific words it uses. There is no "for each neighbor" statement in C, Objective-C, or any other language I know of. If you know what the concept "neighbor" means, then you know how to code it. If you don't know what "neighbor" means, then you'll get lost trying to find a "for each neighbor" looping structure.

So what do you think "neighbor" means, in the context of the algorithm? Does it mean "immediately adjacent to, either in the same row or column" or maybe even including diagonal row and column.


Your second mistake is not recognizing the row,column notation of the algorithm, and relating that to C. In C, a 2D array of rows and columns is addressed by array[row][column]. This is equivalent to array[row,column] in the algorithm description. The latter is common in other languages, just not in C or C-like languages.

Furthermore, Objective-C NSArrays only have one dimension. There's no such thing as row/column addressing of NSArrays. You can, however declare an array of arrays. Each object in the "array of rows" is another array: the columns for that row.


If that's all too confusing, then you're in way over your head, and you need to back off and go review fundamentals. For starters, learn about C arrays and row/column addressing. Then learn the equivalent using NSArray. Finally, figure out what "neighbor" means in a row/column array, and think about how you'd actually implement that. Frankly, you should be able to solve it using plain C, with no NSArrays at all. And even using Objective-C, none of this involves NSDictionary classes, nor format strings.

No, no, that's exactly what I needed. I'm aware in Objective C we do [x][y] but I wasn't sure what the pseudocode meant by [v] or how to interpret that. I had an idea, but it's better to know than guess.

I do understand what it means by neighbour and was able to implement that in my code easily enough, and I wasn't expecting it to be line by line completely but... my code takes it a bit far.

Thanks again.

 

[ArtOfWarfare]

Since you're only moving horizontally and vertically, I would say make your program attempt to do a path going in the correct horizontal and vertical directions... if it tries every combination of only positive horizontal and vertical movements and finds none of them are valid, then it might try solutions where it backtracks once, then twice, etc.

Does that make sense?

 

[MythicFrost]

Since you're only moving horizontally and vertically, I would say make your program attempt to do a path going in the correct horizontal and vertical directions... if it tries every combination of only positive horizontal and vertical movements and finds none of them are valid, then it might try solutions where it backtracks once, then twice, etc.

Does that make sense?

I thought about trying to adapt something like a breadth-first search I found to work with making note of the directions and disregarding unnecessary movements but I couldn't begin to think about it.

I've currently got the Dijkstra's code compiling and running although I've run into a hiccup.

The while loop below never runs since previous is always undefined.

1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]
6  end while ;

I've outputted my array previous (it's an NSMutableArray) and there's nothing in previous[1], but there is some stuff afterwards.

I'm making progress at least... here's the small section that changes previous:

NSArray *neighbours = [self getNeighboursForU:u];
        for (int i = 0; i < neighbours.count; i++) {
            if ([queue containsObject:[neighbours objectAtIndex:i]]) {
                NSString *v = [neighbours objectAtIndex:i];
                
                split = [self getVectorFromString:v];
                int vRow = [[split objectAtIndex:0] intValue];
                int vCol = [[split objectAtIndex:1] intValue];
                
                int vDist = dist[vRow][vCol];
                int uDist = dist[row][col];
                
                int alt = dist[row][col] + (uDist-vDist);
                if (alt < vDist) {
                    dist[vRow][vCol] = alt;
                    [[previous objectAtIndex:vRow] setObject:u atIndex:vCol];
                    
                    int indexOf = [queue indexOfObject:v];
                    [queue removeObject:v];
                    [queue insertObject:v atIndex:indexOf+1];
                }
            }
        }

I've got to get some sleep but I'll post the whole code in the morning if need be... I've tried to make the code as "line by line" as possible, so it's easy to compare to the pseudocode. Cheers.