Archive

Monthly Archives: April 2014

There are a thousand implementations of A* in Java. This one is mine.

EDIT: If you're drawing your maps left to right, top to bottom, you're best off storing your maps as [y][x] to avoid cache misses and to improve data locality. The code below assumes [x][y] because I wrote it for someone else.

import java.awt.Point;
import java.util.ArrayList;

public class AStar {
	public static Point[] findPath(double[][] map, Point start, Point finish) {
		// These are for running A*.
		Point current = null;
		ArrayList  candidates = new ArrayList();
		Point[][] parent = new Point[map.length][map[0].length];
		double[][] cost = new double[map.length][map[0].length]; // All costs start at infinity, but Java inits them to zero.
		double[][] costToGoal = new double[map.length][map[0].length];
		
		// Set initial costs to infinity.
		for(int i=0; i < map.length; i++) {
			for(int j=0; j < map[i].length; j++) {
				cost[i][j] = Float.POSITIVE_INFINITY;
				costToGoal[i][j] = Float.POSITIVE_INFINITY;
			}
		}
		
		// We make start its own parent so that we know it's visited.  
		// This may have problems when reversing, but we can safely do so because we have the start point as an argument.
		parent[start.x][start.y] = start;
		cost[start.x][start.y] = 0;
		costToGoal[start.x][start.y] = heuristic(map, start.x, start.y, finish.x, finish.y);
		
		candidates.add(start);
		while(!candidates.isEmpty()) {
			// Do an O(n) search for the smallest candidate.  In a densely connected graph, a minheap may drive the cost to O(n^2 log n).
			// Since this isn't really densely connected, we could switch for a performance boost.
			Point minCostCandidate = null;
			double minCost = Float.POSITIVE_INFINITY;
			for(Point p : candidates) {
				if(cost[p.x][p.y] + costToGoal[p.x][p.y] < minCost) {
					minCostCandidate = p;
					minCost = cost[p.x][p.y] + costToGoal[p.x][p.y];
				}
			}
			candidates.remove(minCostCandidate);
			current = minCostCandidate;
			
			if(current.equals(finish)) {
				break;
			}
			
			// We've got the shortest path so far.  Now let's figure out the cost of the eight items around this candidate.
			// If a neighbor has a _higher_ cost, make this node the parent and decrease the cost.
			for(int dy=-1; dy<2; dy++) {
				for(int dx=-1; dx<2; dx++) {
					// Short-hand for our neighbor's location.
					int nbrx = current.x+dx;
					int nbry = current.y+dy;
					
					// Make sure it's a valid spot on the map.
					if(dx==0 && dy==0) { continue; } // Skip the current point.  Can't be your own parent.
					if(!isInsideMap(map, nbrx, nbry)) { continue; } // Don't plot outside the map.
					
					// Distance from the start to here plus the distance from here to the neighbor.
					double distToNeighbor = cost[current.x][current.y] + distanceSquared(map, current.x, current.y, nbrx, nbry);
					
					// If we have a faster way to get here, update it!
					if(distToNeighbor < cost[nbrx][nbry]) {
						cost[nbrx][nbry] = distToNeighbor;
						costToGoal[nbrx][nbry] = heuristic(map, nbrx, nbry, finish.x, finish.y);
						parent[nbrx][nbry] = current;
						candidates.add(new Point(nbrx, nbry));
					}
				}
			}
		}
		
		if(!current.equals(finish)) {
			return null; // No path to goal.
		}
		
		ArrayList  prepath = new ArrayList();
		while(!current.equals(start)) {
			prepath.add(current);
			current = parent[current.x][current.y];
		}
		
		Point[] path = new Point[prepath.size()]; // Reverse the path before returning it.
		for(int i=0; i < path.length; i++) {
			path[i] = prepath.get(prepath.size()-1-i);
		}
		return path;
	}
	
	public static boolean isInsideMap(double[][] map, int x, int y) {
		return x >= 0 && x < map.length && y >= 0 && y < map[0].length; 
	}
	
	public static double heuristic(double[][] map, int ax, int ay, int goalx, int goaly) {
		double dx = ax - goalx;
		double dy = ay - goaly;
		double dz = map[ax][ay] - map[goalx][goaly];
		return dx*dx + dy*dy + dz*dz;
	}
	
	public static double distanceSquared(double[][] map, int ax, int ay, int bx, int by) {
		final double UPHILL_COST_SCALAR = 1.0; // Going up hill costs 3x more than going down hill.
		final double DOWNHILL_COST_SCALAR = 1.0; //  Going down hill costs just as much as going flat.
		
		double deltaDistance = (ax-bx)*(ax-bx) + (ay-by)*(ay-by);
		double deltaHeight = map[ax][ay] - map[bx][by];
		if(deltaHeight < 0) {
			deltaHeight = Math.max(0, deltaHeight*DOWNHILL_COST_SCALAR); // We are assuming that moving downhill has a non-negative cost. 
		} else if(deltaHeight > 0) {
			deltaHeight *= UPHILL_COST_SCALAR;
		} else {
			// No change.
		}
		
		return deltaDistance + deltaHeight*deltaHeight;
	}
}

And some helpful main to produce pretty outputs:

	public static void main(String[] args) {
		final int XSIZE = 40;
		final int YSIZE = 40;
		
		// Run this to test.
		double[][] map = new double[XSIZE][YSIZE];
		Random rand = new Random();
		
		for(int i=0; i < XSIZE; i++) {
			for(int j=0; j < YSIZE; j++) {
				map[i][j] = rand.nextInt(2);
			}
		}
		Point start = new Point(rand.nextInt(XSIZE), rand.nextInt(YSIZE));
		Point end = new Point(rand.nextInt(XSIZE), rand.nextInt(YSIZE));
		
		Point[] path = findPath(map, start, end);
		
		// Draw the map
		char[][] output = new char[XSIZE][YSIZE];
		for(int i=0; i < XSIZE; i++) {
			for(int j=0; j < YSIZE; j++) {
				if(map[i][j] != 0) {
					output[i][j] = '#';
				} else {
					output[i][j] = ' ';
				}
			}
		}
		
		// Draw the path on the map.
		if(path != null) {
			for(Point p : path) {
				output[p.x][p.y] = '.';
			}
		}
		
		// Draw the start and end.
		output[start.x][start.y] = 'S';
		output[end.x][end.y] = 'E';
		
		// Print everything.
		for(int j=0; j < YSIZE; j++) {
			for(int i=0; i < XSIZE; i++) {
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	}

And some selected sample output.

     # #  #### # ### # #     ##   #   # 
   ### #E.### ##  ##  ##     #  ####### 
 # # # # #.... ## #   # ##  ## #   # #  
##### #  # ###.##    # ## ## ### # ##  #
## ## #### ## #.# # ## ## #  # ######  #
##   ### # ## ##.# # ## ###    #   #  # 
#### #  ### #   #.# ###### ## # ###### #
 #  ##    ##  ### .########## #   ## #  
    ## # #  ##     . # ##### # # # #####
 ###   #  ###   ##  .   #     ##    ####
#      ##  #  #### # .##  ### ##  ##### 
##   ##    # #  # ####S # # #    # ### #

 

#   #  #  #   # #  ## # ## # #######  ##
# ##### #  #   #   #  #. ##    ###..# # 
## ##  ## ##........... .......... #E# #
 ######   #.  ##   # ## #  ##    ## # ##
 #   ## ##.## ##   # # #  ###  ####   ##
## #    #. #      #  ## # #      ###  # 
 #### ##.###  #####    ### # #### # ### 
#  # ##.   # ####  #   ###  # #   ##    
 #### S# #    ####     #  ### #  ##  ###
  ##  #  ##  # #   #  ## #  ##### ## ###
#  ## ## #  # #     # ##    ## ### # ## 

Last weekend I was tasked with throwing together an Android application for a friend with a neurological disorder. Without going into the details, it required some simple bookkeeping like, "Did I take my medicine," "Did I remember to lock the door," and things of the sort. I figured it would be a good introductory project for a semi-seasoned Java developer to get into Android development. I'd done a little bit before -- odd projects like Morsey and MethRacer, but none thus far have been native applications. After I started, I realized why. Despite the abundance of documentation and tutorials on Android, I could never quite fit together how the application was supposed to flow for any examples beyond the most trivial 'Hello World'. It seemed like the practice never quite synced with the preaching and the tutorials that showed the logical flow were either too dated or basic to really make things stick. I asked for help on the SomethingAwful forums and got a spectacular response. I'm reproducing it here so that other people with similar problems in their mental models might take solace.

Some beginner conceptual questions here. I'm not grokking the logical flow of the average Android app. I can use Buttons in Views to signal Intents which trigger changes to new Activities which have different Views, yes? Or have I completely lost it? Fragments, then, are when you have n ways of looking at the same data and don't want to pass it between activities?

Almost immediately, poster Uncomfortable Gaze responded with this elucidation.

That's a bit off. This is a bit complicated so I apologize in advance if I make things worse.

Views are simply UI elements, combined together inside ViewGroups to form the interface. Buttons are just a type of view, one specifically designed around its onClick function. Most views can actually be used like a button, the base View class that every UI element extends from has onClick callbacks. Most of the UI elements you need already exist (TextView/ImageView/EditText/ect). Treat them like lego blocks, plug them in wherever you need them then control them from the parent Activity or Fragment.

Activities encapsulate those views and handle lifecycle and most interaction logic. An activity should contain the UI logic for a "page" (for lack of a better term). For example, you could have a single activity to handle a login process, and another activity to show a list of content items, and another one to display the actual content itself. The lifecycle is the change between states in the activity when launching or exiting. This hopefully explains the whole cycle better than I ever could.

Intents are essentially messages used to start new activities, send broadcasts, and do more advanced stuff. The most basic use is to start a new activity, for example: when the user completes the login, you would call startActivity() with an intent that pointed to your next activity, like the content list. You can include extra data in that intent, and it's typical to include enough information that the target activity knows exactly what it needs to do. The intent used to start an activity is always accessible by calling getIntent(), and the intent has get_Extra() methods to grab that extra data.

Fragments are essentially sub-activities, they replicate most of the functionality of an Activity but must be placed within an Activity. They were introduced to allow for multi-pane layouts on tablets and are great for code re-use. You can design a content-list fragment and a content-view fragment, then on a tablet you can place both side-by-side in the same activity. Otherwise on a phone you can show just the content-list fragment, then when someone selects an item it starts a new activity that only has the content-view fragment. Most of the activity logic can be moved into the fragment, and that fragment can be inserted into any activity. If your just starting out, it might be a good idea to start with a normal Activity. You'll need to learn fragments at some point though, most modern apps depend on them.

It's probably a good idea to just start here and keep reading. Maybe get a book as well. (I have no idea what book to recommend)

Within the span of one minute, Karthe responded with this tidbit:

Activities host Fragments. That is, Activities should be containers in which Fragments sit and do their thing. For the most part, a Fragment class will contain most of a screen's logic and will handle the heavy lifting of preparing the screen for viewing. The Activity handles stuff like setting up the ActionBar and loading a Fragment into itself. The main benefit of splitting things up like this is that Fragments can be easily dropped into another Activity that uses a different layout. This would come in handy if you were developing an app that has a different layout on tablets - an Activity can be set up to use a different layout depending on the screen size, so you can reuse Fragments and code instead of writing multiple classes for all different kinds of devices.

Views are just the base class of the structural classes like ListView and LinearLayout. They define the structure of the content.

You can set onClickListeners on Buttons. In that listener, you can do something like define an Intent that will pass along some information to a new Activity or Fragment. The information can be accessed in either's onCreate() to initialize whatever you want. Whatever activity you launch can have completely different logic or appearance from the Activity or Fragment launching the activity.

Here are some tutorials that might help you wrap your head around the Android way of doing things:
http://developer.android.com/training/basics/activity-lifecycle/index.html
http://developer.android.com/training/basics/fragments/index.html
This is a great place to start, it starts with the basics and moves into more advanced topics: http://developer.android.com/training/index.html

This is why Goons are amazing.