Java/Processing: A* graph node based game

Tags: , , ,



I am trying to build a little ‘simulation’ game. This game has no real purpose, I am just making small little projects while I try and learn the in’s and out’s of some beginner programming.

This is my goal:

  1. On the processing canvas, there are multiple ‘Nodes’ that represent where a player can move to.
  2. The user will input where the player is and where they want to move to. (referencing the nodes)
  3. The program will determine the most efficient route using the A* algorithm.
  4. Once the route has been determined, the player (represented by a Circle()) will move from node to node in a straight line.
  5. Once the player has stopped, the program will know which node the player is currently at AND will wait for further instructions.

I have somehow managed to scrape together the first three of my goals but the second half has been causing me major confusion and headaches.

What I have tried (Goal 4). I am using a custom library for the A* algorithm which can be found here: http://www.lagers.org.uk/pfind/ref/classes.html. When the algorithm drew the lines for the optimal route, I would store the X,Y position of each node into an ArrayList. I would then feed that ArrayList data into my Player Class that would move the circle on the screen via the X/Y positions from the ArrayList. The issue I had, is that once the player moved to the first node, I had no way of reporting that the player had stopped moving and is ready to move onto the next ArrayList X/Y position. I managed a workaround by incrementing the ArrayList every 5 seconds using Millis() but I know this is a terrible way of achieving my goal.

This probably does not make a lot of sense but here is a picture of my current output. Text

I have told the program that I want the Blue Circle to travel from Node 0 to Node 8 on the most efficient route. My current code would move copy the X/Y positions of Node 0,2,8 and save them into an ArrayList. That ArrayList information would be fed into the player.setTarget() method every 5 seconds to allow time for the circle to move.

Ideally, I would like to scrap the time delay and have the class report when the player has moved to the node successfully AND which node the player is currently on.

import pathfinder.*;
import java.lang.Math;

// PathFinding_01
Graph graph;
// These next 2 are only needed to display 
// the nodes and edges.
GraphEdge[] edges;
GraphNode[] nodes;
GraphNode[] route;
// Pathfinder algorithm
IGraphSearch pathFinder;

// Used to indicate the start and end nodes as selected by the user.
GraphNode startNode, endNode;

PImage bg;
Player midBlue;
Player midRed;
int lastHittingBlue = 99;
int lastHittingRed = 99;
int blueSide = 0;
int redSide = 1;
boolean nodeCount = true;
boolean firstRun = true; //Allows data to be collected on the first node.
boolean movement;
int count;
int x;
int y;
float start;
float runtime;
int test = 1;

// create ArrayList for route nodes 
ArrayList<Float> xPos; 
ArrayList<Float> yPos;


void setup() {
  size(1200,1000);    //Set size of window to match size of the background image. 
  bg = loadImage("background.png");
  bg.resize(1200,1000);
  
  start = millis();
  
  textSize(20);
  // Create graph
  createGraph();
  // Get nodes and edges
  nodes = graph.getNodeArray();
  edges = graph.getAllEdgeArray();
  // Now get a path finder object
  pathFinder = new GraphSearch_Astar(graph);
  // Now get a route between 2 nodes
  // You can change the parameter values but they must be valid IDs
  pathFinder.search(0,8);
  route = pathFinder.getRoute();
  
  //Initialise the X/Y position arraylist.
  xPos = new ArrayList<Float>();
  yPos = new ArrayList<Float>();

  drawGraph();
  drawPath();

  midBlue = new Player(lastHittingBlue, blueSide);
  midRed = new Player(lastHittingRed, redSide);
  
}

void draw() {
  background(0);
  
  text((float)millis()/1000, 10,height/6);
  text(start/1000, 10,height/3);
  runtime = millis() - start;
  text(runtime/1000, 10,height/2);
  
  if (runtime >= 5000.0) {
    start = millis();
    float printX = midBlue.getXPos();
    float printY = midBlue.getYPos();
    int pX = round(printX);
    int pY = round(printY);
    print(pX, " ", pY, "n");
    test += 1;
  }
  
  drawGraph();
  drawPath();
  
  movement = midBlue.movementCheck();
  midBlue.setTargetPosition(xPos.get(test), yPos.get(test));

  midBlue.drawPlayer();

  text( "x: " + mouseX + " y: " + mouseY, mouseX + 2, mouseY );

  //noLoop();
}

void drawGraph() {
  // Edges first
  strokeWeight(2);
  stroke(180, 180, 200);
  for (int i = 0; i < edges.length; i++) {
    GraphNode from = edges[i].from();
    GraphNode to = edges[i].to();
    line(from.xf(), from.yf(), to.xf(), to.yf());
  }
  // Nodes next
  noStroke();
  fill(255, 180, 180);
  for (int i = 0; i < nodes.length; i++) {
    GraphNode node = nodes[i];
    ellipse(node.xf(), node.yf(), 20, 20);
    text(node.id(), node.xf() - 24, node.yf() - 10);
  }
}

void drawPath() {
  strokeWeight(10);
  stroke(200, 255, 200, 160);
  for (int i = 1; i < route.length; i++) {
    GraphNode from = route[i-1];
    GraphNode to = route[i];
    
    while (firstRun) {      
      xPos.add(from.xf());
      yPos.add(from.yf());
      firstRun = false;
    }
    
    xPos.add(to.xf());
    yPos.add(to.yf());
    
    line(from.xf(), from.yf(), to.xf(), to.yf());
    
    if (nodeCount == true) {
       count = route.length;
       nodeCount = false;
    }
    
  }
}


public void createGraph() {
  graph = new Graph();
  // Create and add node
  GraphNode node;
  //                   ID   X    Y
  node = new GraphNode(0, 175, 900);
  graph.addNode(node);
  node = new GraphNode(1, 190, 830);
  graph.addNode(node);
  node = new GraphNode(2, 240, 890);
  graph.addNode(node);
  node = new GraphNode(3, 253, 825);
  graph.addNode(node);
  node = new GraphNode(4, 204, 750);
  graph.addNode(node);
  node = new GraphNode(5, 315, 770);
  graph.addNode(node);
  node = new GraphNode(6, 325, 880);
  graph.addNode(node);
  node = new GraphNode(7, 440, 880);
  graph.addNode(node);
  node = new GraphNode(8, 442, 770);
  graph.addNode(node);
  node = new GraphNode(9, 400, 690);
  graph.addNode(node);
  node = new GraphNode(10, 308, 656);
  graph.addNode(node);
  node = new GraphNode(11, 210, 636);
  graph.addNode(node);

  // Edges for node 0
  graph.addEdge(0, 1, 0, 0);
  graph.addEdge(0, 2, 0, 0);
  graph.addEdge(0, 3, 0, 0);
  // Edges for node 1
  graph.addEdge(1, 4, 0, 0);
  graph.addEdge(1, 5, 0, 0);
  graph.addEdge(1, 10, 0, 0);
  // Edges for node 2
  graph.addEdge(2, 5, 0, 0);
  graph.addEdge(2, 6, 0, 0);
  graph.addEdge(2, 8, 0, 0);
  // Edges for node 3
  graph.addEdge(3, 5, 0, 0);
  graph.addEdge(3, 8, 0, 0);
  graph.addEdge(3, 10, 0, 0);
  // Edges for node 4
  graph.addEdge(4, 10, 0, 0);
  graph.addEdge(4, 11, 0, 0);
  // Edges for node 5
  graph.addEdge(5, 8, 0, 0);
  graph.addEdge(5, 9, 0, 0);
  graph.addEdge(5, 10, 0, 0);
  // Edges for node 6
  graph.addEdge(6, 7, 0, 0);
  graph.addEdge(6, 8, 0, 0);
  // Edges for node 7
  graph.addEdge(7, 0, 0, 0);

    // Edges for node 7
  graph.addEdge(9, 0, 0, 0);
    // Edges for node 7
  //graph.addEdge(10, 0, 0, 0);
    // Edges for node 7
  graph.addEdge(11, 0, 0, 0);
}


class Player {
  int lastHitting;
  int side; //0 = Blue, 1 = Red.
  float xPos;
  float yPos;
  float xTar;
  float yTar;
  color circleColour = color(255,0,0);
  boolean isPlayerStopped;
  int xDir;
  int yDir;
  
  Player(int lastHitting, int side) {
    this.lastHitting = lastHitting;
    this.side = side;
    
    /* Set the Colour of the circle depending on their side selection */
    if (this.side == 0) { 
      circleColour = color(0,0,255);
      xPos = 180;
      yPos = 900;
    } else if (this.side == 1) {
      circleColour = color(255,0,0);
      xPos = 990;
      yPos = 125;
    }
  }
  
  
  void drawPlayer() {
    fill(circleColour);
    circle(xPos,yPos,35);
    
    float speed = 100.0;
    PVector dir = new PVector(xTar - xPos, yTar - yPos);
    
    while (dir.mag() > 1.0) {
      dir.normalize();
      dir.mult(min(speed, dir.mag()));
      
      xPos += dir.x;
      yPos += dir.y;
      isPlayerStopped = false;
    }
    
    if (dir.mag() < 1.0) {
      isPlayerStopped = true;
    }
  }
  
  
  void setTargetPosition(float targetX, float targetY) {
    xTar = targetX;
    yTar = targetY;
  }
  
  
  boolean movementCheck() {
     return isPlayerStopped;
  }
  
  float getXPos() {
    return xPos;
  }
  
  float getYPos() {
    return yPos;
  }
  
  
  
  
}

Thank you for your help in advance. I know this is a bit of a loaded question. I am really just looking for direction, I have tried a lot of different things and I’m not sure what tool I am supposed to use to help me progress.

Please don’t flame my terrible code too much, I am still very new to all of this.

Answer

I am not going to flame your terrible code because I know how steep the learning curve is for what you’re doing and I respect that. This said, I think that you would gain much more insight on what’s going on if you ditched the library and coded your A* yourself.

If it comes to that, I can help later, but for now, here’s what we’ll do: I’ll point out how you can get this result:

Smooth moves

And as a bonus, I’ll give you a couple tips to improve on your coding habits.


I can see that you kinda know what you’re doing by reading your own understanding of the code (nice post overall btw), but also in the code I can see that you still have a lot to understand about what you’re really doing.

You should keep this exactly as it is right now. Email it to yourself to you receive in in one year, this way next year while you despair about getting better you’ll have the pleasant surprise to see exactly how much you improved – or, in my case, I just decided that I had been retarded back then and still was, but I hope that you’re not that hard on yourself.

As there is A LOT of space for improvement, I’m just going to ignore all of it except a couple key points which are not project specific:

  1. Use explicit variable names. Some of your variables look like they are well named, like nodeCount. Except that this variable isn’t an integer; it’s a boolean. Then, it should be named something like nodesHaveBeenCounted. Name your variables like if an angry biker had to review your code and he’ll break one of your finger every time he has to read into the code to understand what’s a variable purpose. While you’re at it, try not to shorten a variable name even when it’s painfully obvious. xPos should be xPosition. This apply to method signatures, too, both with the method’s name (which you’re really good at, congrats) and the method’s parameters.

  2. Careful with the global variables. I’m not against the idea of using globals, but you should be careful not to just use them to bypass scope. Also, take care not to name local variables and global variables the same, like you did with xPos, which may be an ArrayList or a float depending where you are in the code. Be methodic: you can add something to all your global variables which clearly identify them as globals. Some people name prefix them with a g_, like g_xPos. I like to just use an underscore, like _xPos.

  3. When a method does more than one thing, think about splitting it in smaller parts. It’s waaay easier to debug the 8 lines where a value is updated than to sift through 60 lines of code wondering where the magic is happening.

Now here are the changes I made to make the movements smoother and avoid using a timer.

In the global variables:

  1. Rename xPos into xPosArray or something similar, as long as it’s not overshadowed by the Player’s xPos modal variable. Do the same with the yPos ArrayList.

In the setup() method:

  1. Add this line as the last line of the method (as long as it’s after instantiating midBlue and running the drawPath method it’ll be right):

midBlue.setTargetPosition(xPosArray.get(test), yPosArray.get(test));

In the draw() method:

  1. Remove the if (runtime >= 5000.0) {...} block entirely, there’s no use for it anymore.

  2. Remove these lines:

movement = midBlue.movementCheck();
midBlue.setTargetPosition(xPosArray.get(test), yPosArray.get(test));

In the Player.drawPlayer() method:

Erase everything after and including the while. Replace it with these lines (they are almost the same but the logic is slightly different):

if (dir.mag() > 1.0) {
  dir.normalize();
  dir.mult(min(speed, dir.mag()));

  xPos += dir.x;
  yPos += dir.y;
} else {
  // We switch target only once, and only when the target has been reached
  setTargetPosition(xPosArray.get(test), yPosArray.get(test));
}

Run the program. You don’t need a timer anymore. What’s the idea? It’s simple: we only change the Player’s target once the current target has been reached. Never elsewhere.

Bonus idea: instead of a global variable for your array of coordinates, each player should have it’s own ArrayList of coordinates. Then each Player will be able to travel independently.

Have fun!



Source: stackoverflow