CODEWITHSUNDEEP
javaalgorithmshortest-path
Kiwi
Kiwi

Reputation: 2773

Java shortest path

I'm trying to make an small tower defender game in Java. I have a grid that is made up of a Point2D.Double array named:

FieldArr[h][v]

h represents horizontal fields, v the vertical vertical fields

this makes a grid like this

+ + + + + + +
S + X + + + +
+ + + X + + +
+ X + + + + F
+ + X + + + +

S represents start, F represents Finish, X represents Towers

now I want to calculate the shortest route for but i don't have any clue how to start on this

Towers have the following vars for location: HorizontalNr and VerticalNr.

for paint I do then:

public void paint(Graphics2D g2) {
    int Xpos = HorizontalNr * playfield.getSquarewidth() + playfield.GetinitialXPos();
    int Ypos = VerticalNr * playfield.getSquarewidth() + playfield.GetinitialYPos();
    g2.fillRect(Xpos, Ypos, 50, 50);
}

Anyone have any tips, on how I should make my enemy class, so I won't get in any problem with the algorithm? and/or have tips on how to calculate the shortest path?

already thanks grt kiwi

Upvotes: 0

Views: 4180

Answers (3)

amit
amit

Reputation: 178521

As Mark said, this is Shortest Path Problem, which can be solved easily and efficiently.

Note, that since your problem is not weighted, you can use a BFS here, which is pretty easy to implement and also guarantees finding sortest path for unweighted graphs.

Pseudo code for BFS:

findShortestPath(source,target):
  queue<- new queue
  visited <- {}
  Map<point,point> parents <- empty map
  queue.push(source)
  while (queue.empty() == false): 
     current <- queue.takeFirst()
     if (current.equals(target)):
         extract the path from source to destination using the map parents(*)
         return
     visited.add(current)
     for each p such that p and current are neighbors: //insert neighbors to queue
          if p is not in visited: 
                if (p is not an obstacle):
                   queue.push(p)
                   parents.put(p,current) //current is the parent of p

(*) Extracting the path from the map is simple: just follow the current <- parent.get(current) until you get null, this way you extract the exact path you will use.

Note that even faster solution [in most cases] will be A* with the manhattan distance heuristic, but it is much more complex to implement it.

Upvotes: 1

Paul
Paul

Reputation: 53

if you're looking to avoid the towers then your looking for the euclidean path from start to finish, which is solvable with a shortest path approach ala djkstra.

Upvotes: 2

Mark Byers
Mark Byers

Reputation: 839214

The shortest path problem has been studied a lot and a lot of literature exists on this problem. It's probably best to just using an existing algorithm rather than trying to invent an algorithm yourself.

For example, a simple and efficient algorithm is Dijkstra's algorithm. From Wikipedia:

  1. Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
  2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
  3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
  5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
  6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.

Upvotes: 4

Related Questions