Java help needed

[HalfTangible]

So for AI, I need to put together and implement an A* pathfinding... thing to find the shortest path from start to goal on a grid.

Which I do not have the slightest clue how to do. There's something called a binary heap, i know that. And the sides are all length 1 or somthing, and... @_@ Last thing I did with this stuff was GUIs, I'm confused.


In this project you are asked to implement A* to run a series of experiments and report your results and conclusions.
You can us
e the programming language of your preference to implement and visualize the results of your
algorithms. You can work in pairs. Please inform the instructor who are the members of your team.
Answer the following questions under the assumption that A* are
used on eight
-
neighbor grids. Average all
experimental results over the same 50 eight
-
neighbor grids of size 100
×
50 with 10 percent randomly blocked
cells and randomly chosen start and goal vertices so that there exists a path from the start vertex to th
e goal vertex.
You need to generate these grids yourself. Remember that we assumed that paths can pass through vertices where
diagonally touching blocked cells meet. All search algorithms search from the start vertex to the goal vertex.

[Drumbum42]

I hate to state the obvious, but are you allowed to get outside help? It states that you can have a partner, but most teachers frown upon students getting a team of internet goers to assist you.

Not to be "that guy," but Colleges (which I am assuming this is for) generally have policies with strict disciplinary action about such things. I just don't want to bring friendly fire upon a fellow playgrounder.

(I had a friend that was threatened with expulsion for something similar)

[HalfTangible]

I hate to state the obvious, but are you allowed to get outside help? It states that you can have a partner, but most teachers frown upon students getting a team of internet goers to assist you.

Not to be "that guy," but Colleges (which I am assuming this is for) generally have policies with strict disciplinary action about such things. I just don't want to bring friendly fire upon a fellow playgrounder.

(I had a friend that was threatened with expulsion for something similar)

It's allowed as long as I'm not asking you to write the code for us :smalltongue: Advice, debugging and similar are okay as far as I know.

[factotum]

The only time I ever did something like this (which was 20 years ago!), I used an algorithm which populated the grid with numbers--I started with 1 at the starting location, put 2 in every square which could be reached in 1 move from that location, then 3 in the squares 1 move from those locations that didn't already have numbers in, etc. (How to actually do this is left as an exercise for the reader :smallwink:). You can then create your route by counting back down from the end square--say that square has ended up with the value 6 in it, you get a route by counting back 5, 4, 3, 2, 1.

I have no idea if this is even close to what they're expecting you to do, but I offer it as an idea.

[EDIT] Having looked up some info about the A* algorithm, I'm really not sure the above *is* what they're looking for, so best ignore it...

[Felyndiira]

This site does a good job of explaining the algorithm:

http://www.policyalmanac.org/games/aStarTutorial.htm

[Douglas]

The only time I ever did something like this (which was 20 years ago!), I used an algorithm which populated the grid with numbers--I started with 1 at the starting location, put 2 in every square which could be reached in 1 move from that location, then 3 in the squares 1 move from those locations that didn't already have numbers in, etc. (How to actually do this is left as an exercise for the reader :smallwink:). You can then create your route by counting back down from the end square--say that square has ended up with the value 6 in it, you get a route by counting back 5, 4, 3, 2, 1.

I have no idea if this is even close to what they're expecting you to do, but I offer it as an idea.

[EDIT] Having looked up some info about the A* algorithm, I'm really not sure the above *is* what they're looking for, so best ignore it...
That is a way to find a route, and even the shortest route, but it is most definitely not A* and therefore not applicable to this assignment.

The ingredients of an A* algorithm:
1) A way to estimate the remaining distance to travel, using only where you are and where you want to go without bothering to examine anything in between, that is guaranteed to not be an overestimate. Ideally it should also be achievable if what's in between turns out to be perfect.
2) A stored set of places you've already found paths to.
3) Storage for the length of the paths to each place you've found a path to.
4) A way to find the place in item 2 that has the smallest total of distance to get to it plus the estimate from 1 for how far it still has to go.

2 should start out as simply the start location with a path length of 0.

Once you have those, simply get the location from 4, remove it from 2 so it won't show up in 4 again, take all locations directly adjacent to it and add them to 2, and repeat until you're at the destination. For retrieving the actual path, you can either build it up along the way and store it along with the path lengths, or you can backtrack from the end.

It might help for understanding the algorithm to draw up a grid on paper, put some random blocks in it, and run through the steps on paper. You'll have to come up with something for ingredient 1, but the appropriate function should be pretty obvious for this.