|
- package gr.auth.ee.dsproject.pacman;
-
- import java.util.ArrayList;
-
- import gr.auth.ee.dsproject.node.Globals;
- import gr.auth.ee.dsproject.node.Tree;
- import gr.auth.ee.dsproject.node.Node89978445;
-
- /**
- * <p>
- * Title: DataStructures2011
- * </p>
- *
- * <p>
- * Description: Data Structures project: year 2011-2012
- * </p>
- *
- * <p>
- * Copyright: Copyright (c) 2011
- * </p>
- *
- * <p>
- * Company: A.U.Th.
- * </p>
- *
- * @author Michael T. Tsapanos
- * @version 1.0
- */
-
- public class Creature implements gr.auth.ee.dsproject.pacman.AbstractCreature
- {
-
- public String getName () {
- return "Mine";
- }
-
- private int step = 1;
- private boolean amPrey;
-
- public Creature (boolean isPrey) {
- amPrey = isPrey;
- }
-
- /**
- * @brief
- * For any current position creates a tree for minmax alpha-beta pruning algorithm
- * apply the min-max algo and return the move representing by resulting node
- * @return
- * the move of pacman to play
- */
- public int calculateNextPacmanPosition (Room[][] Maze, int[] currPosition)
- {
- int [] bestPos = {-1, -1}; // Best position in maze to play
- int bestMove = 0;
- Node89978445 bestNode; // The node with the best evaluation
- Node89978445 cur = new Node89978445 (Maze, currPosition); // The node with the current position
-
- //make the tree
- createSubTreePacman (cur.getDepth (), cur, Maze, currPosition);
-
- // min-max to find best node and consequently the best position
- bestNode = Tree.minmaxAB (cur, Globals.MINMAXTREE_MAX_DEPTH-1, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
- bestPos = bestNode.getCurrentPacmanPos();
-
- // convert back to move encoding
- if ((bestMove = Node89978445.moveConv (bestPos, currPosition)) != Globals.INVALID_MOVE)
- return bestMove;
- else
- return 0;
- }
-
- /**
- * @brief
- * For any ghost (or root) parent node, create all child nodes representing
- * pacman's valid moves.
- * @note
- * This routine calls createSubTreeGhosts() called back from it recursively.
- * The recursion ends when the right depth is reached.
- */
- void createSubTreePacman (int depth, Node89978445 parent, Room[][] Maze, int[] curPacmanPosition)
- {
- if (depth >= Globals.MINMAXTREE_MAX_DEPTH-1)
- /*<
- * As the depth starts from 0 and MINMAXTREE_MAX_DEPTH
- * is strictly even, with this comparison we accept that there
- * is no need for a max-depth layer of ghosts-evaluation based nodes.
- * As soon as we accept the depth-1 layers max evaluated node.
- */
- return;
- else {
- Node89978445 newNode;
- Room[][] newMaze;
- int[] nextPosition = {-1, -1};
-
- // scan possible valid moves
- for (int move=0 ; move<4 ; ++move) {
- if ((nextPosition = Node89978445.pacmanValidMove (parent, move)) != Globals.POSITION_FALSE) {
- // Make a copy of the maze in order to simulate next move and move Pacman
- newMaze = PacmanUtilities.copy (Maze);
- PacmanUtilities.movePacman (newMaze, parent.getCurrentPacmanPos(), nextPosition);
-
- // Create a node for the move in the new stated game maze
- newNode = new Node89978445 (newMaze, nextPosition);
- Tree.grow (newNode, parent); // add node to the min-max search tree
-
- // call the recursive branch creator
- createSubTreeGhosts (newNode.getDepth (), newNode, newMaze, newNode.getCurrentGhostPos());
- }
- }
- }
- }
-
- /**
- * @brief
- * For any parent node, create all child node representing ghosts valid moves.
- * @note
- * This routine recursively call createSubTreePacman().
- * The recursion ends when the right depth is reached.
- */
- void createSubTreeGhosts (int depth, Node89978445 parent, Room[][] Maze, int[][] currGhostsPosition)
- {
- if (depth >= Globals.MINMAXTREE_MAX_DEPTH-1)
- /*<
- * As the depth starts from 0 and MINMAXTREE_MAX_DEPTH
- * is strictly even, with this comparison we accept that there
- * is no need for a max-depth layer of ghosts-evaluation based nodes.
- * As soon as we accept the depth-1 layers max evaluated node.
- */
- return;
- else {
- Node89978445 newNode;
- Room[][] newMaze;
- ArrayList<int[][]> ghostMoves;
-
- // Get all possible ghost moves
- ghostMoves = PacmanUtilities.allGhostMoves(Maze, currGhostsPosition);
-
- // loop all ghost moves
- for (int i=0 ; i<ghostMoves.size() ; ++i) {
- // Make a copy of the maze in order to simulate next move and move ghosts
- newMaze = PacmanUtilities.copy (Maze);
- PacmanUtilities.moveGhosts(newMaze, currGhostsPosition, ghostMoves.get(i));
-
- // Create a node for the move in the new stated game maze
- newNode = new Node89978445 (newMaze, parent.getCurrentPacmanPos());
- Tree.grow (newNode, parent); // add node to the min-max search tree
-
- //recursive call for the rest of the tree
- createSubTreePacman (newNode.getDepth (), newNode, newMaze, parent.getCurrentPacmanPos());
- }
- }
- }
-
- public int[] getPacPos (Room[][] Maze)
- {
- int[] pacmanPos = new int[2];
- for (int i = 0; i < PacmanUtilities.numberOfRows; i++) {
- for (int j = 0; j < PacmanUtilities.numberOfColumns; j++) {
- if (Maze[i][j].isPacman()) {
- pacmanPos[0] = i;
- pacmanPos[1] = j;
- return pacmanPos;
- }
- }
- }
- return pacmanPos;
- }
-
- public boolean[] comAvPos (Room[][] Maze, int[][] currentPos, int[] moves, int currentGhost)
- {
-
- boolean[] availablePositions = { true, true, true, true };
-
- int[][] newPos = new int[4][2];
-
- for (int i = 0; i < 4; i++) {
-
- if (Maze[currentPos[currentGhost][0]][currentPos[currentGhost][1]].walls[i] == 0) {
- availablePositions[i] = false;
- continue;
- }
-
- if (PacmanUtilities.flagColision(Maze, currentPos[currentGhost], i)) {
- availablePositions[i] = false;
- }
-
- else if (currentGhost == 0)
- continue;
-
- else {
- switch (i) {
- case Room.WEST:
- newPos[currentGhost][0] = currentPos[currentGhost][0];
- newPos[currentGhost][1] = currentPos[currentGhost][1] - 1;
- break;
- case Room.SOUTH:
- newPos[currentGhost][0] = currentPos[currentGhost][0] + 1;
- newPos[currentGhost][1] = currentPos[currentGhost][1];
- break;
- case Room.EAST:
- newPos[currentGhost][0] = currentPos[currentGhost][0];
- newPos[currentGhost][1] = currentPos[currentGhost][1] + 1;
- break;
- case Room.NORTH:
- newPos[currentGhost][0] = currentPos[currentGhost][0] - 1;
- newPos[currentGhost][1] = currentPos[currentGhost][1];
-
- }
-
- for (int j = (currentGhost - 1); j > -1; j--) {
- switch (moves[j]) {
- case Room.WEST:
- newPos[j][0] = currentPos[j][0];
- newPos[j][1] = currentPos[j][1] - 1;
- break;
- case Room.SOUTH:
- newPos[j][0] = currentPos[j][0] + 1;
- newPos[j][1] = currentPos[j][1];
- break;
- case Room.EAST:
- newPos[j][0] = currentPos[j][0];
- newPos[j][1] = currentPos[j][1] + 1;
- break;
- case Room.NORTH:
- newPos[j][0] = currentPos[j][0] - 1;
- newPos[j][1] = currentPos[j][1];
- // break;
- }
-
- if ((newPos[currentGhost][0] == newPos[j][0]) && (newPos[currentGhost][1] == newPos[j][1])) {
-
- availablePositions[i] = false;
- continue;
- }
-
- if ((newPos[currentGhost][0] == currentPos[j][0]) && (newPos[currentGhost][1] == currentPos[j][1]) && (newPos[j][0] == currentPos[currentGhost][0])
- && (newPos[j][1] == currentPos[currentGhost][1])) {
-
- availablePositions[i] = false;
-
- }
- }
- }
- }
-
- return availablePositions;
- }
-
- public int comBestPos (boolean[] availablePositions, int[] pacmanPosition, int[] currentPos)
- {
-
- int[] newVerticalDifference = new int[2];
- for (int i = 0; i < 2; i++)
- newVerticalDifference[i] = currentPos[i] - pacmanPosition[i];
-
- int[] distanceSquared = new int[4];
-
- for (int i = 0; i < 4; i++) {
- if (availablePositions[i] == true) {
-
- switch (i) {
- case Room.WEST:
- newVerticalDifference[1]--;
- break;
- case Room.SOUTH:
- newVerticalDifference[0]++;
- break;
- case Room.EAST:
- newVerticalDifference[1]++;
- break;
- case Room.NORTH:
- newVerticalDifference[0]--;
- break;
- }
- distanceSquared[i] = newVerticalDifference[0] * newVerticalDifference[0] + newVerticalDifference[1] * newVerticalDifference[1];
- } else
- distanceSquared[i] = PacmanUtilities.numberOfRows * PacmanUtilities.numberOfRows + PacmanUtilities.numberOfColumns * PacmanUtilities.numberOfColumns + 1;
- }
-
- int minDistance = distanceSquared[0];
- int minPosition = 0;
-
- for (int i = 1; i < 4; i++) {
- if (minDistance > distanceSquared[i]) {
- minDistance = distanceSquared[i];
- minPosition = i;
- }
-
- }
-
- return minPosition;
- }
-
- public int[] calculateNextGhostPosition (Room[][] Maze, int[][] currentPos)
- {
-
- int[] moves = new int[PacmanUtilities.numberOfGhosts];
-
- int[] pacmanPosition = new int[2];
-
- pacmanPosition = getPacPos(Maze);
- for (int i = 0; i < PacmanUtilities.numberOfGhosts; i++) {
- moves[i] = comBestPos(comAvPos(Maze, currentPos, moves, i), pacmanPosition, currentPos[i]);
- }
-
- return moves;
-
- }
-
- public boolean[] checkCollision (int[] moves, int[][] currentPos)
- {
- boolean[] collision = new boolean[PacmanUtilities.numberOfGhosts];
-
- int[][] newPos = new int[4][2];
-
- for (int i = 0; i < moves.length; i++) {
-
- if (moves[i] == 0) {
- if (currentPos[i][1] > 0) {
- newPos[i][0] = currentPos[i][0];
- newPos[i][1] = currentPos[i][1] - 1;
- } else {
- newPos[i][0] = currentPos[i][0];
- newPos[i][1] = PacmanUtilities.numberOfColumns - 1;
- }
-
- } else if (moves[i] == 1) {
- if (currentPos[i][0] < PacmanUtilities.numberOfRows - 1) {
- newPos[i][0] = currentPos[i][0] + 1;
- newPos[i][1] = currentPos[i][1];
- } else {
- newPos[i][0] = 0;
- newPos[i][1] = currentPos[i][1];
- }
- } else if (moves[i] == 2) {
- if (currentPos[i][1] < PacmanUtilities.numberOfColumns - 1) {
- newPos[i][0] = currentPos[i][0];
- newPos[i][1] = currentPos[i][1] + 1;
- } else {
- newPos[i][0] = currentPos[i][0];
- newPos[i][1] = 0;
-
- }
- } else {
- if (currentPos[i][0] > 0) {
- newPos[i][0] = currentPos[i][0] - 1;
- newPos[i][1] = currentPos[i][1];
- } else {
-
- newPos[i][0] = PacmanUtilities.numberOfRows - 1;
- newPos[i][1] = currentPos[i][1];
-
- }
- }
-
- collision[i] = false;
- }
-
- for (int k = 0; k < moves.length; k++) {
-
- }
-
- for (int i = 0; i < moves.length; i++) {
- for (int j = i + 1; j < moves.length; j++) {
- if (newPos[i][0] == newPos[j][0] && newPos[i][1] == newPos[j][1]) {
-
- collision[j] = true;
- }
-
- if (newPos[i][0] == currentPos[j][0] && newPos[i][1] == currentPos[j][1] && newPos[j][0] == currentPos[i][0] && newPos[j][1] == currentPos[i][1]) {
-
- collision[j] = true;
- }
-
- }
-
- }
- return collision;
- }
-
- }
|