Jump to content
  • Advertisement
Sign in to follow this  
padam

how to create a map of square grids to implement a* algorithm ?

This topic is 3643 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone. I am creating a 2D strategy game based on basic AI i.e i am implementing a* pathfinding algorithm to move my game character on map. I have gone through the vaious tutorial on net and understood the concept.But i am having difficulty on creating square grid map. I have created a class called node for each square grid. /* * To change this template, choose Tools | Templates * and open the template in the editor. */ package rts.maps; /** * * @author Netbeans */ public class Node { private int f; private int g; private int h; // heuristic value public final int Y; public final int X; private Node parent; private boolean justLocation; public Node (int y, int x, int g, int h) { this.Y = y; this.X = x; if (g == 0 && h == 0) { justLocation = true; } else { this.g = g; this.h = h; this.f = this.g + this.h; justLocation = false; } } public Node (int y, int x, int g, int h, Node parent) { this(y, x, g, h); this.parent = parent; } public int compareF(Node node) { return (this.f - node.f); } public boolean equals(Node node) { if (node.Y == this.Y && node.X == this.X) { return true; } else { return false; } } public Node getParent() { return this.parent; } public int getF() { return this.f; } public int getG() { return this.g; } public int getH() { return this.h; } public void setParent(Node parent) { this.parent = parent; } public void setG(int g) { this.g = g; this.f = this.g + this.h; } @Override public String toString() { String line; if (this.justLocation == true) { line = "(Y: " + this.Y; line += ", X: " + this.X + ")"; } else { line = "(Y: " + this.Y; line += ", X: " + this.X; line += ", F: " + this.f; line += ", G: " + this.g; line += ", H: " + this.h + ")"; } return line; } } This class refers to each node or square for map. So now pls help me to create a grid map. I have been trying for past 2 days but could not come up with any result.Just an idea. Thanks. Note: i am using Java 2D [Edited by - padam on December 22, 2008 11:40:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
Nodes are the locations of each spot on the grid, however you generally also need edges which show what node is connected to what (or in your case what node is next to another node). If you want to make it work in the case that you can go from A to B to C but also say A to Z (where they are not touching each other on a map but can somehow warp to it) then you should use edges to connect them. Each node will have it's location on a 2D matrix (if it's small enough to not cause problems). However I am sure there are better ways to do it, this is just one idea.

Share this post


Link to post
Share on other sites
Sorry but,how to create a map.
size of my game character is 50*50 pixels and i want to move my character in a map. Suppose i want to create 5*5 grid map i.e 25 grids. How do i create this map. First i want to create a map then i am gonna apply a*. And i am using edges as u said so that i could access its adjacent sides.
Thanks.

Share this post


Link to post
Share on other sites

You are using a cartesian mapping system that has a one to one correlation with a 2 dimensional array. The nodes are the elements of this array and use the adjacent nodes as neighbors -- either the 4 flat sided adjacents or with 8 neighbors including the diagonals from each grid square node.

The edges connecting the nodes are regualrized to be movements of +/- along the x and y axis of the array -- being something like dx[8] = { 0,1,1,1,0,,-1,-1,-1} dy[8] = {-1,-1,0,1,1,1,0,-1} with a loop 0..7 to step thru the 8 edge directions. You will have to be careful of the edges of the array so as not to try to access coordinate values larger than the array dimensions. Sometimes it is easier to have an extra buffer row/column map edge marked with NoMovement terrain so you dont have to do extra range tests on calculated coordinates.

Your Closed list is done by marking a flag in your map array. The best path cost to that node could be stores as part of the array also.

You would have to decide how to calculate the movement difficulty (edge cost) either by content of that map grid node (ie- terrain type) and/or from the height info for each node if you have any.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!