• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
tom_mai78101

A* algorithm by pixel: Failed to create diagonal path in 3x3 grid.

5 posts in this topic

I have trouble creating a path, either it's closed or best, from going downwards (south) and / or diagonally downwards (southeast / southwest).

Here's a picture displaying the current state of my program (bugged, and inaccurately displayed) :

[img]http://i1207.photobucket.com/albums/bb464/tom_mai78101/Untitled-5.png[/img]

I have set Square 1 as my starting point, and Square 9 as my finishing point. From Square 1 to Square 9, I set the default colors to different hues of dark red. From Square 1 to Square 3, those are the squares added into the "best" array list selected out, and marked as white to distinguish as the "best path" from starting point to finishing point.

I expected to have Square 1, Square 2, Square 5, Square 6, and Square 9 (Or 1, 4, 5, 8, and 9) be marked white, and all three of the squares are added to the "best" array list. The picture above is not what I wanted.

I'm asking for help in determining where my bug occurred, where the "best" path is unabled to be generated correctly. One major problem is that my source code is pretty huge when considering how jumpy my code is.

Currently, I'm reading through my codes to try and figure out where it's not working.

Source code, place where I suspect it's where the bug is located at. I probably narrowed it down quite a lot:

[CODE]
package core;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
public class Grid
{
public List<Square> grids = new ArrayList<Square>();
public List<Square> exists = new ArrayList<Square>();
public int size = 9;
public int width;
public int height;
public Square target = new Square(0, this);
// =======================================================
public int rows = 0;
public int columns = 0;
public Square goal;
public Square[][] squares;
public List<Square> opened = new ArrayList<Square>();
public List<Square> closed = new ArrayList<Square>();
public List<Square> best = new ArrayList<Square>();
int xStart = 0;
int yStart = 0;
int xFinish = 2;
int yFinish = 2;

public Grid(int rows, int columns)
{
this.rows = rows;
this.columns = columns;
this.squares = new Square[rows][columns];
int count = 0;
for(int j = 0; j < rows; j++)
{
for(int i = 0; i < columns; i++)
{
this.squares[j][i] = new Square(count++, this);
this.squares[j][i].setCoordinate(j, i);
}
}
squares[xStart][yStart].setFlag(Square.START);
squares[xFinish][yFinish].setFlag(Square.FINISH);
this.goal = squares[xFinish][yFinish];
for(int ro = 0; ro < squares.length; ro++)
for(int c = 0; c < squares[ro].length; c++)
squares[ro][c].checkAdjacencies();
}

public void findingPath()
{
Set<Square> adjacSet = squares[xStart][yStart].adjacencies;
for(Square adjacent : adjacSet)
{
adjacent.parent = squares[xStart][yStart];
if(adjacent.flag != Square.START)
opened.add(adjacent);
}
}

public Square findBestPath()
{
Square best = null;
Square goal = null;
for(int i = 0; i < squares.length; i++)
for(int j = 0; j < squares[i].length; j++)
if(squares[i][j].flag == Square.FINISH)
goal = squares[i][j];
for(Square square : opened)
{
if(best == null || square.getCost(goal) < best.getCost(goal))
{
best = square;
}
}
return best;
}

// ============================================
private void populateBestList(Square square)
{
best.add(square);
if(square.parent.flag != Square.START)
populateBestList(square.parent);
return;
}
boolean testFlag = false;

public void tick()
{
if(testFlag == false)
{
findingPath();
testFlag = true;
}
if(opened.size() > 0)
{
Square best = findBestPath();
opened.remove(best);
closed.add(best);
if(best.flag == Square.FINISH)
{
populateBestList(goal);
return;
}
else
{
Set<Square> neighbors = best.adjacencies;
for(Square neighbor : neighbors)
{
if(opened.contains(neighbor))
{
Square temp = new Square(neighbor.id, this);
temp.setCoordinate(neighbor.x, neighbor.y);
temp.parent = best;
if(temp.getCost(goal) >= neighbor.getCost(goal))
continue;
}
if(closed.contains(neighbor))
{
Square temp = new Square(neighbor.id, this);
temp.setCoordinate(neighbor.x, neighbor.y);
temp.parent = best;
if(temp.getCost(goal) >= neighbor.getCost(goal))
continue;
}
neighbor.parent = best;
opened.remove(neighbor);
closed.remove(neighbor);
opened.add(0, neighbor);
}
}
}
if(opened.size() <= 0)
{
Square temp = null;
for(Square t : best)
if(t.flag == Square.FINISH)
temp = t;
while(temp != null)
{
temp = temp.parent;
}
}
}

public void render(int[] pixels)
{
for(Square object : closed)
{
pixels[object.x + object.y * width] = object.color;
}
}
}
[/CODE]

Thanks for your help in reading this thread in advance.
0

Share this post


Link to post
Share on other sites
Your A* implementation is a little unconventional. Skimming through the code I've noticed the following things:
[list=1]
[*]Your closed list logic is a little off. You should test to see if a neighbour is in the closed list, and if it is, ignore it and move on, since the closed list represents tiles you've already visited.
[*]Similarly, you shouldn't ever be removing entries from the closed list.
[*]Neither should you be removing the neighbouring squares from the open list in the neighbour checking loop.
[*]It also seems that if the cost function test fails in the part where you check to see if the neighbour is in the open list, it will end up adding the neighbour to the open list again a little bit later in the code.
[*]Why do you recalculate the goal square in findBestPath()?
[/list]

Incidentally, what's your getcost() function look like?
0

Share this post


Link to post
Share on other sites
Sorry for not replying a week ago. Been busy with real life.

[quote name='Postie' timestamp='1329781573' post='4914997']
Your closed list logic is a little off. You should test to see if a neighbour is in the closed list, and if it is, ignore it and move on, since the closed list represents tiles you've already visited.[list=1]
[*]Similarly, you shouldn't ever be removing entries from the closed list.
[*]Neither should you be removing the neighbouring squares from the open list in the neighbour checking loop.
[*]It also seems that if the cost function test fails in the part where you check to see if the neighbour is in the open list, it will end up adding the neighbour to the open list again a little bit later in the code.
[/list]
[/quote]

I guess Points 1 and 2 are valid. Under what scenarios should I remove a neighbor or a grid from the opened list and/or closed list?

As for the cost function test, I'm not clearly in the picture on the subject of creating a condition that evaluates whether the neighbor is allowed to be in the open list while not determining whether that same neighbor satisfies itself being in the closed list.

What I'm saying is that, there may be two or more possible solutions. For example, I expected two different solutions, so I couldn't create a more specific condition when calculating the cost for the squares and parents individually. My hypothesis is, if I used "greater than or equals to" condition, I might be able to satisfy all conditions in this situation, but I didn't. I'm all ears on the cost function test problem, and how I should rethink my logic on this part.

[quote name='Postie' timestamp='1329781573' post='4914997']
4. Why do you recalculate the goal square in findBestPath()?
[/quote]

Shouldn't it be included in the total cost from a parent square to the target square?

[quote name='Postie' timestamp='1329781573' post='4914997']
Incidentally, what's your getcost() function look like?
[/quote]

Here you go!

[CODE]
private double getLocalCost(Square goal){
if (this.flag == Square.START)
return 0.0;
localCost = 1.0 * (Math.abs(x - goal.x) + Math.abs(y - goal.y));
return localCost;
}

public double getParentCost(){
if (this.flag == Square.START)
return 0.0;
if (parentCost == 0.0)
parentCost = 1.0 + 0.5 * (this.parent.getParentCost() - 1.0);
return parentCost;
}

public double getCost(Square goal){
if (this.flag == Square.START)
return 0.0;
return getLocalCost(goal) + getParentCost();
}
[/CODE]
0

Share this post


Link to post
Share on other sites
Hi tom_mai.

Have a look at your local cost function. Much like the silly [url="http://www.gamedev.net/topic/589301-pi--4-discuss/"]Pi=4[/url] topic which szecs presented on GameDev some time ago,
(in which the circle is thought to have the same circumference as its bounding square), the fastest way to the diagonally opposite corner is just as well along the edges as it is across:

Right, Right, Down Down
you'd like it to be
Right, Down, Right, Down

It's the same cost, so it's not an advantage to pick the latter over the former.

Your local cost function is [color=#006666]1.0[/color][color=#000000] [/color][color=#666600]*[/color][color=#000000] [/color][color=#666600]([/color][color=#660066]Math[/color][color=#666600].[/color][color=#000000]abs[/color][color=#666600]([/color][color=#000000]x [/color][color=#666600]-[/color][color=#000000] goal[/color][color=#666600].[/color][color=#000000]x[/color][color=#666600])[/color][color=#000000] [/color][color=#666600]+[/color][color=#000000] [/color][color=#660066]Math[/color][color=#666600].[/color][color=#000000]abs[/color][color=#666600]([/color][color=#000000]y [/color][color=#666600]-[/color][color=#000000] goal[/color][color=#666600].[/color][color=#000000]y[/color][color=#666600]));[/color]
(why the multiplication by the way?)

And that's not the same as the direct distance across. (Cost function still makes sense, though. if the agent cannot move diagonally)
If you want it to go across, get the actual distance between the centers of each square: (Pythagoras is your friend)

[color=#800080]Math[/color][color=#666600].[/color]sqrt[color=#666600]( [/color][color=#666600]([/color][color=#000000]goal[/color][color=#666600].[/color][color=#000000]x-x[/color][color=#666600])*[/color][color=#666600]([/color][color=#000000]goal[/color][color=#666600].[/color][color=#000000]x-x[/color][color=#666600])[/color][color=#000000] [/color][color=#666600]+[/color][color=#000000] [/color][color=#666600][color=#666600]([/color][color=#000000]goal[/color][color=#666600].[/color][color=#000000]y-y[/color][color=#666600])*[/color][color=#666600]([/color][color=#000000]goal[/color][color=#666600].[/color][color=#000000]y-y[/color][color=#666600]) [/color]);[/color]
0

Share this post


Link to post
Share on other sites
First of all, sorry for not responding earlier. This post dropped off my radar and I forgot to follow it up.

You should only be removing items from the open list when you traverse them. That is, at the very top of the processing loop you search the open list for the node with the lowest cost. Once you find it, you remove it from the open list, then test to see if that node is in the closed list. If it is, then you loop back to the start and find the next node. Otherwise, you add the node to the closed list, and proceed with the rest of the processing using that node. You should never remove nodes from the closed list, as this represents nodes that you've already visited.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0