// This is a stand-alone test of the ghost algorithms. // Not 100% finished yet but the hard parts are in place. // This should be relatively easy to add to the 6809 code // as long as it doesn't use too much RAM. Note that some // experimentation and logging of results will be needed // to ensure that we can get away with byte-sized variables // in the various large arrays that wil be needed (eg for // the breadth-first searching of the maps). #include #ifndef EXIT_FAILURE extern void exit(int rc); #define EXIT_FAILURE 1 #define EXIT_SUCCESS 0 #endif typedef int bool; #ifndef FALSE #define TRUE (0==0) #define FALSE (0!=0) #endif #define DEBUG_Q 1 /* Optimal Pacman Ghost Algorithm. Before I start, allow me to head off some comments that I know several people will be dying to make: 1) I am aware (in detail) of the algorithms used in the originals. You do not need to explain them to me. 2) I am aware that the algorithm here is by default very deadly and will make the game much harder if it were the only strategy being used. It won't be. But I do need to know the most powerful algorithm for the hardest levels. The overall strategy is to look ahead to certain places to where Puck can move from its current position, and identify 4 target locations which Puck *must* go through. These locations are specifically the junctions at the ends of corridors which can be found by searching outwards from his current location (using a breadth-first search, which is basically a flood-fill) until 4 junctions have been reached. The ghosts are then assigned one of these targets each, as a destination, and they take the shortest and fastest route from their current location to that target. One strategy for assigning ghosts to each target is as follows: As there are 4 ghosts and 4 targets, there are 4 factorial (24) different assignments of ghost-to-target possible - the best matching of ghost to target being determined by an evaluation function that takes one of the 24 permutations as one parameter, and the 4X4 ghost-to-target matrix as the other parameter. This evaluation function is applied to all 24 permutations and the best one is returned as the one to be acted on. Each ghost now has its own position and a target position. A breadth-first search to connect each pair gives us the route that the ghost must follow to get to its target. However an alternative strategy - which does not target those four choke points - that will cost far less CPU to implement - is to continue the breadth-first fill that was started from the Puck position until the expanding front has touched all 4 ghosts. Then the ghosts paths are the reverse path of that fill. This strategy might be invoked only in certain circumstances. Also the ghost 'fleeing' strategy might be to move in the direction immediately opposite to that flood fill result. One of the reasons that we *don't* use this as the default ghost strategy is that it frequently leads to the ghosts trailing behind Puck and never catching him. Because Puck is always moving, the algorithm above would appear not to handle a moving Puck. But in fact it can be made to do so extemely easily! Simply move each ghost one step on each frame, recalculating from scratch on the next frame! You might think that this rapid recalculation would cause jittery movement by the ghosts, continually reversing themselves, but in practice it does not - 1) because the Puck's destination options change only when it reaches a junction; and 2) the ghosts can only change direction (which includes reversing their path down a corridor) when they are *at* a junction themselves. The overall result is that they follow a consistent path and do not change that path unless it makes sense to do so. Note that once the ghosts have reached the target points, they should switch to heading directly to the Puck. This overall strategy (with the exception of the optimised assignment of ghosts to targets) has been implemented before, in my "ScratchMan" program at the MIT Scratch site. */ // NOTE: ROWS*COLS == 868 ... a byte array of [ROWS][COLS] is damned close to the // entire free RAM on the Vectrex. We *cannot* afford more than one array of these // dimensions. We might not even be able to afford one. #define ROWS 31 #define COLS 28 static const char* wallmap0[ROWS] = { "############################", "# ## ## #", "# #### ## ######## ## #### #", "# #### ## ######## ## #### #", "# #", "### ## ##### ## ##### ## ###", " # ## # # ## # # ## # ", "### ## ##### ## ##### ## ###", " ## ## ## ", "### ##### ######## ##### ###", " # ##### ######## ##### # ", " # # ", " # ##### ### ### ##### # ", " # ##### # # ##### # ", " # ## # # ## # ", " # ## ## # # ## ## # ", "### ## ## ######## ## ## ###", " ## ## ", "### ######## ## ######## ###", " # ######## ## ######## # ", " # ## # ", " # ##### ######## ##### # ", "### ##### ######## ##### ###", "# #", "# #### ##### ## ##### #### #", "# # # ##### ## ##### # # #", "# # # ## ## ## # # #", "# # # ## ######## ## # # #", "# #### ## ######## ## #### #", "# #", "############################", }; #define LEFT 0 #define RIGHT 1 #define UP 2 #define DOWN 3 const int directions[4] = {LEFT, RIGHT, UP, DOWN}; // Movements for BFS traversal (LEFT, RIGHT, UP, DOWN) const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; // position in the maze plus current direction vector typedef struct Actor { int X, Y; int dx, dy; // These need really only be 1 bits each. // Since X and Y are both <= 31 (i.e. use only 5 bits), // We could easily store dx packed into X and dy into Y // especially if we use C bitfields to make them more // readable. (See also 'visited') } Actor; Actor Player; // Player's X,Y coordinate Actor Ghost[4]; // Ghosts' positions Actor Explorer; // Used when exploring the map looking for junctions etc, and by BFS search. // A basic queue implementation for BFS #define MAX_Q_CAPACITY (ROWS*COLS) // Absolute upper limit. Trim later for Vectrex. typedef struct Queue { Actor data[MAX_Q_CAPACITY]; int front, rear, size; } Queue; #ifdef DEBUG_Q int max = 0; // We can't afford 31x28 matrix in Ram on the 6809. How much do we actually need? #endif #define MAX_DISTANCE 127 int distance[ROWS][COLS]; bool visited[ROWS][COLS]; // Could be squeezed into distance[][] array? // Either by 1) Reserving one value for unvisited (255?) // or by 2) using a single bit for visited (0x80). // It would be especially valuable on the Vectrex is // we could reuse this array for Queue.data as well. #define N 4 // Number of ghosts and their target destinations // Table of distances between each ghost and each target. // Initial values are for testing only. static int distanceMatrix[N][N] = { {9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4} }; #define PERMS (4*3*2*1) // This is the re-ordering of ghosts that will be used to assign each ghost to a specific target destination: int bestPerm; // There are only 24 possible ways to assign ghosts to targets so why not evalulate them all and pick the best one? int order[PERMS][N] = { {0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 0, 3, 2}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0}, {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0} }; // Having identified the 4 targets (choke points) we are going to use, this evaluation // function should tell us which is the best assignment of a ghost to a destination // (using whichever criterion we can think of that gives us a 'best'). Initial criterion // is to arrange for the arrival of the ghosts at the choke points to happen as close to // simultaneously as possible. // If that doesn't work well in practice we can try others by rewriting this function. // An alternative function could take into account the distance of the targets from // the player, and attempt to optimise earliest arrivals at the nearest targets... // The 'HungarianAlgorithm' code in an earlier version chasing.c (in RCS) - although // it is optimising for total distance travelled - actually does quite well for that // option, although it may be rather expensive to evaluate using the HungarianAlgorithm ... // however it might be a lot cheaper to simply *check* all the 24 permutations for a // compatible result! // Our initial cost function minimizes the differences between each ghost's travel time: int balanced(int thisPermutation) { // lower value of cost function means better fit int targetDistance; // The rather verbose arithmetic expressions below ensure that we do not assign a value // in excess of the largest number that can be stored in a distance variable, which will // be relevant when we move the code to the Vectrex and want to store distances in a // single byte in order to reduce RAM usage. int D0 = distanceMatrix[0][order[thisPermutation][0]], D1 = distanceMatrix[1][order[thisPermutation][1]], D2 = distanceMatrix[2][order[thisPermutation][2]], D3 = distanceMatrix[3][order[thisPermutation][3]]; targetDistance = (D0>>2) + (D1>>2) + (D2>>2) + (D3>>2) + (((D0&3) + (D1&3) + (D2&3) + (D3&3) + 2/*rounding*/)>>2); D0 -= targetDistance; D1 -= targetDistance; D2 -= targetDistance; D3 -= targetDistance; return D0*D0 + D1*D1 + D2*D2 + D3*D3; // Calculate the squared differences from the target distance } // Find the best assignment of ghosts to targets by trying all 24 possible orderings (i.e. every // permutation of the 4 targets against the 4 ghosts). Assign the result to global 'bestPerm': void evaluateBestAssignment(int (*costFunction)(int thisPermutation)) { int thisPerm, thisCost, bestCost = MAX_DISTANCE; for (thisPerm = 0; thisPerm < PERMS; thisPerm++) { // Loop over all 24 permutations and look for if ((thisCost = costFunction(thisPerm)) < bestCost) { // the permutation with the *LOWEST* overall cost bestCost = thisCost; bestPerm = thisPerm; } } } // Print the assignments of ghost to destination, and the distance // travelled by each ghost. For development debugging only. void printAssignmentsAndDistances(void) { int ghost, target; printf("Ghost/Target matrix: (each row is a ghost, each column is a possible target)\n"); for (ghost = 0; ghost < N; ghost++) { printf(" ghost %d: ", ghost); for (target = 0; target < N; target++) { printf("%d, ", distanceMatrix[ghost][target]); } printf("\n"); } printf("\nAssignment of ghosts to target junctions:\n"); for (ghost = 0; ghost < N; ghost++) printf("Ghost %d -> Target %d distance = %d\n", ghost + 1, order[bestPerm][ghost] + 1, distanceMatrix[ghost][order[bestPerm][ghost]]); } static inline int Path(Actor *M, int direction) { // Is movement possible in the requested direction? // TO DO!!! Needs speial handling for wraparound tunnels. Best if handled at a higher level than this. return wallmap0[M->Y + dy[direction]][M->X + dx[direction]] == ' '; } // Our modified Dijkstra algorithm produces truly deadly behaviour by the ghosts - // but we do not always want them to be so accurate. I will be writing code to // implement a less deadly algorithm, roughly based on the original games. // Code to decide when to switch algorithms remains to be designed. // Expedient queue management for now - when I move this to the Vectrex it will need to // be a static array of fixed length, implementing a cyclic buffer. By then I should have // a reasonable estimate of the largest size of the array that's needed. // Function to create a queue Queue queue; void ReinitialiseQueue(void) { queue.front = queue.size = 0; // PUT AND GET POINTERS WOULD BE BETTER. size should not be needed. queue.rear = MAX_Q_CAPACITY - 1; } // Function to enqueue a position into the queue void Enqueue(Actor pos) { if (queue.size == MAX_Q_CAPACITY) { fprintf(stderr, "Queue is full.\n"); exit(EXIT_FAILURE); } queue.rear = (queue.rear + 1) % MAX_Q_CAPACITY; // Warning. Expensive on 6809 unless power of 2 queue.data[queue.rear] = pos; queue.size++; #ifdef DEBUG_Q if (queue.size > max) max = queue.size; #endif } // Function to dequeue a position from the queue. Result passed back via a global variable 'Explorer' void DequeueExplorer(void) { Explorer = queue.data[queue.front]; queue.front = (queue.front + 1) % MAX_Q_CAPACITY; // Warning. Expensive on 6809 unless power of 2 queue.size--; } int DistanceToPlayer(int ghostno) { // DistanceToPlayer function using BFS int row, col, dir, newX, newY, dist; if (wallmap0[Ghost[ghostno].Y][Ghost[ghostno].X] != ' ') { fprintf(stderr, "Ghost at %d,%d is not on a path\n", Ghost[ghostno].X, Ghost[ghostno].Y); exit(EXIT_FAILURE); } // If the ghost is already at the player's position, return 0 if (Ghost[ghostno].X == Player.X && Ghost[ghostno].Y == Player.Y) return 0; // Create a queue for BFS and a visited array, plus a distance array to store // the number of steps to reach each position - unfortunately distances have // to be at least a byte per entry which will take up some space. At least // the 'visited' array can be an array of bits, though if merged with Distance // it could be done away with altogether - it depends on the max value of any // distance, but I'm fairly sure this will be OK... ReinitialiseQueue(); for (row = 0; row < ROWS; row++) { for (col = 0; col < COLS; col++) { distance[row][col] = MAX_DISTANCE; // Initialize distances to infinity visited[row][col] = FALSE; } } // Enqueue the starting ghost position Enqueue(Ghost[ghostno]); visited[Ghost[ghostno].Y][Ghost[ghostno].X] = TRUE; // Visited and distance could be merged... (MAX_DISTANCE: false >=0: true) distance[Ghost[ghostno].Y][Ghost[ghostno].X] = 0; // Distance to the starting point is 0 // to do: check that distances never exceed 255? 127? and see if we can use bytes. // Perform BFS while (queue.size != 0) { // size may not be needed. a check of put/get pointers is all that's really needed in a cyclic list. DequeueExplorer(); // Explore all 4 possible directions for (dir = 0; dir < 4; dir++) { newX = Explorer.X + dx[dir]; newY = Explorer.Y + dy[dir]; // Check if it's a valid move and if there's a path in that direction if ((!visited[newY][newX]) && Path(&Explorer, dir)) { visited[newY][newX] = TRUE; // Mark the position as visited distance[newY][newX] = distance[Explorer.Y][Explorer.X] + 1; // If we reach the player's position, return the distance if (newX == Player.X && newY == Player.Y) { dist = distance[newY][newX]; #ifdef DEBUG_Q fprintf(stderr, "Maximum number of queue elements that will need to be allocated = %d\n", max); #endif return dist; // Return the shortest distance to the player } // Enqueue the new position. Actually a function of 'Explorer' taking into account junctions and corners, // so this is not finished yet. It will be important if/when we record the path back to the Puck. Actor newPos = {newX, newY, 0, 0}; Enqueue(newPos); } } } /* NOT REACHED */ // C really should not complain about this. return MAX_DISTANCE; // bleh } int main(int argc, char **argv) { int SimplePlayerDist; // Actor Target[4]; Player.X = 13; // Player's X coordinate Player.Y = 23; // Player's Y coordinate Player.dx = -1; Player.dy = 0; Ghost[0].X = 6; Ghost[0].Y = 2; Ghost[0].dx = 0; Ghost[0].dy = 1; SimplePlayerDist = DistanceToPlayer(0); // When there are no junctions left between a ghost and the player, the ghost will // switch to direct pursuit mode. This has not yet been written. // To implement the identification of targeted junctions (outlined below), we need // to write some support functions that will determine the ends of corridors when // travelling in the current direction, taking into account forced L-shaped corner // turns. (No algorithmic comlexity here, just tricky and careful code writing). // For example, fork = GetFork(Player.X, Player.Y, Player.dx, Player.dy) if ((Path(&Player, LEFT)?1:0) + (Path(&Player, RIGHT)?1:0) + (Path(&Player, UP)?1:0) + (Path(&Player, DOWN)?1:0) == 2) { // Player is in a corridor // Find 3 places to target in the directon the player is moving // First, identify the next fork in the road, but don't target it itself: // fork1 = EndOfCorridor(Player.X, Player.Y, Player.dx, Player.dy); // fork2 = end of corridor for first exit at fork1 excluding where we just came from // fork3 = end of corridor for second exit at fork1 excluding path immediately above, and where we just came from // choose one of fork2 or fork3, and set it as a target //Target[0] = fork2; // set fork4 and fork5 to the end of the corridors on the other fork (say fork3) and set them as targets //Target[1] = fork4; //Target[2] = fork5; // Target[3] = EndOfCorridor(Player.X, Player.Y, -Player.dx, -Player.dy); // and one place to target if he reverses direction //} else if (... == 4) { // at a crossroads. Easy solution - target the ends of all 4 corridors with all 4 ghosts. } else { // Player is at a junction // Target[0] = end of corridor for first exit here excluding where we just came from // Target[1] = end of corridor for second exit here excluding path immediately above, and where we just came from // for Target[2], look at Target[0] and Target[1], and choose the target which is closer. // Then set target 0 or 1 to one of the exists at that point and target 2 to the other // Target 3 remains behind us, in case the player reverses direction // Target[3] = EndOfCorridor(Player.X, Player.Y, -Player.dx, -Player.dy); } // Having identified 4 targets, assign each one to a ghost ... intelligently, using the 4x4 matrix of distance from // target to ghost. fprintf(stderr, "\nShortest Distance from ghost 0 to player is %d\n\n", SimplePlayerDist); evaluateBestAssignment(balanced); printAssignmentsAndDistances(); #ifdef DEBUG_Q fprintf(stderr, "\nFinal maximum number of queue elements that will need to be allocated = %d\n", max); #endif exit(EXIT_SUCCESS); return EXIT_FAILURE; }