terrain cost

Java 2D
#1

Need to implement a terrain cost on a 2D map any advice on how to do it?
Are there any good solution to adopt?
Any lib to use?
I’m really new to the subject so any idea is welcome.
Thanks
Luca

#2

Your question doesn’t really mean anything.

I think you mean to ask: I wish to develop a pathfinding solution for a 2D map which contains terrain cost information. Is that right?

Cas :slight_smile:

#3

Yes sorry for the bad description.
L

#4

A*
http://www.cokeandcode.com/node/1087

#5

Below is a simple, unoptimized A* implementation. It has a main method to test it out in a JFrame. I suggest trying to implement it yourself first using Wikipedia, or at least being sure you understand what the below is doing, still using Wikipedia. Ask questions for all the parts you don’t understand.

import java.awt.Color;
import java.awt.GridLayout;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.util.ArrayList;
import java.util.HashSet;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class PathFinder {
	ArrayList<Node> open = new ArrayList();
	HashSet<Node> closed = new HashSet();
	int width, height;
	int[][] map;
	int targetX, targetY;
	int startX, startY;
	private JFrame frame;

	public static void main (String[] args) {
		PathFinder p = new PathFinder();
		p.width = 18;
		p.height = 16;
		p.map = new int[p.width][p.height];
		p.map[4][1] = -1;
		p.map[4][2] = -1;
		p.map[4][3] = -1;
		p.startX = 2;
		p.startY = 2;
		p.targetX = 16;
		p.targetY = 12;
		p.run();
	}

	private void run () {
		frame = new JFrame();
		frame.getContentPane().setLayout(new GridLayout(height, width, 5, 5));
		frame.addMouseMotionListener(new MouseMotionListener() {
			public void mouseDragged (MouseEvent e) {
			}

			public void mouseMoved (MouseEvent e) {
				startX = (int)(e.getX() / 800f * width);
				startY = (int)(e.getY() / 600f * height);
				update();
			}
		});
		frame.setSize(800, 600);
		frame.setLocationRelativeTo(null);
		frame.setVisible(true);
		update();
	}

	void update () {
		frame.getContentPane().removeAll();
		ArrayList<int[]> path = go();
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				JPanel panel = new JPanel();
				panel.setOpaque(true);
				panel.setBackground(map[x][y] == 0 ? Color.black : Color.red);
				if (path != null) {
					for (int[] coord : path)
						if (x == coord[0] && y == coord[1]) panel.setBackground(Color.green);
				}
				if (x == startX && y == startY) panel.setBackground(Color.blue);
				if (x == targetX && y == targetY) panel.setBackground(Color.blue);
				frame.getContentPane().add(panel);
			}
		}
		frame.validate();
	}

	public ArrayList<int[]> go () {
		long start = System.nanoTime();

		open.clear();
		closed.clear();

		Node root = new Node(null, startX, startY, 0);
		open.add(root);

		while (!open.isEmpty()) {
			int lowestIndex = -1;
			int lowestCost = Integer.MAX_VALUE;
			for (int i = 0, n = open.size(); i < n; i++) {
				Node node = open.get(i);
				int cost = node.g + node.h;
				if (cost < lowestCost) {
					lowestCost = cost;
					lowestIndex = i;
				}
			}

			Node check = open.remove(lowestIndex);
			if (check.x == targetX && check.y == targetY) {
				ArrayList<int[]> path = new ArrayList();
				while (check != root) {
					path.add(0, new int[] {check.x, check.y});
					check = check.parent;
				}

				long end = System.nanoTime();
				System.out.println((end - start) / 1000000f);

				return path;
			}
			closed.add(check);

			addNode(check, check.x, check.y + 1, 10);
			addNode(check, check.x, check.y - 1, 10);
			addNode(check, check.x + 1, check.y, 10);
			addNode(check, check.x - 1, check.y, 10);
			addNode(check, check.x + 1, check.y + 1, 14);
			addNode(check, check.x - 1, check.y - 1, 14);
			addNode(check, check.x + 1, check.y - 1, 14);
			addNode(check, check.x - 1, check.y + 1, 14);
		}

		return null;
	}

	private void addNode (Node parent, int x, int y, int cost) {
		if (x < 0 || y < 0) return;
		if (x >= width || y >= height) return;
		if (map[x][y] != 0) return;
		Node node = new Node(parent, x, y, cost);
		if (closed.contains(node)) return;
		int existingIndex = open.indexOf(node);
		if (existingIndex == -1) {
			open.add(node);
		} else {
			Node existing = open.get(existingIndex);
			if (node.g < existing.g) {
				existing.parent = parent;
				existing.g = node.g;
			}
		}
	}

	private class Node {
		public Node parent;
		public int x, y;
		public int g, h;

		public Node (Node parent, int x, int y, int cost) {
			this.parent = parent;
			this.x = x;
			this.y = y;
			g = parent == null ? 0 : parent.g + cost;
			h = Math.abs(x - targetX) + Math.abs(y - targetY);
			h *= 10;
		}

		public int hashCode () {
			int result = 1;
			result = 31 * result + x;
			result = 31 * result + y;
			return result;
		}

		public boolean equals (Object object) {
			Node node = (Node)object;
			return node.x == x && node.y == y;
		}
	}
}
#6

Thanks will look at it!!!
L