- All coordinates are in pixels, with the usual (Java) pixel-based coordinate system for images, with the origin (0,0) being the upper left corner of the image, and the bottom-right-most point being at coordinate ( w, h ) where w and h are the width and height of the image, respectively.
- Your program must return a PATH from S to G consisting of a sequence of adjacent points on the terrain map.
- Points are considered ADJACENT if they differ by no more than one point in either or both of their x and y coordinates (in other words they are in each other's Moore neighborhoods; see "COST function" below). Note that two adjacent points can be very apart in height; height difference does not affect adjacency.
- Your program must return a Java List of Java Points representing the shortest path, with the start point S at the start of the list and goal point G at the end of the list.
- Your code must also save a file named "shortestPath" containing a Java List object with the shortest path in it, as specified in GOAL item 4 above.
- From any one pt. (i.e., state) there are only eight possible moves (operations): N,NE, E, SE, S, SW, W, NW. This means one pixel in any of the four cardinal directions or any of the four diagonal directions. This is also known as the Moore neighborhood of adjacent points.
- The cost of any such move will be the 3D distance
- Delta x and Delta y are both either 0 or 1, for this assignment, and Delta h is the difference IN THE RED COLOR COMPONENT between the two end points of the move (see the terrain code below).
- Note how the squaring removes any effect of the SIGN of the difference in (x,y,h) coordinate components (e.g., it costs the same to move uphill as it does to go downhill!).
- dsfasd
- Here is an example terrain, with 3D visualization (left), 2D texture or "skin" (center), and 2D heightmap (right):
-
- You will need, at the very least, the jpg version of the height map file (for the terrain above, just click on rightmost image).
- You will need to get the height map file into your java program, and then you will need to get the pixel values into an int array. There is code (below) to do this...
- You might also want to read in the skin file to use information from that, or you might use it for plotting your path so that you can visualize the plan.
- Here is some code that reads in terrain images (as jpg's), displays
them, and allows the user to click on pixels and get their RGB values.
Try it!
- Code is here. Try it. Run it. The sample code needs the following two files: Terrain3map.jpg and Terrain3.jpg.
- Self-explanatory, but if you want to learn more, go to Richard G Baldwin's site, where I learned what I needed for this.
- Another page that was somewhat helpful was at Gamelan at developer.com.
- Sun's Java Docs
-
Here is a paper with Java A* code applied to path finding.
- Possible sources (or
roll your own):
- STRANGERS' CODE:
- Geert-Jan's A* from www.gameai.com (looks good, but I have not tried it myself...)
- Some XML-controlled Java code
- David Brackeen's article has code in it
- Here is a paper with Java A* code applied to path finding.
- OUR CODE
- STRANGERS' CODE:
- Possible sources (or
roll your own):
- Start with our Java search code, because it works! (It compiles and runs, on the Farmer-Goat-Wolf-Cabbage problem...)
- Modify it to implement A* search on one of the three problem domains above.
- Try to stick to this modified interface for State (that way maybe, just maybe, we can interchange each other's search code and problem code [dream on...]):
