A* Algorithim

A* is a popular pathfinding algorithm, and is often used in 2D games for finding the shortest path between two places.

How It Works :


It works by using two different lists : an open list and a closed list.
The open list contains all “open” spaces, or spaces that have not been traversed yet. The closed list contains all spaces that have already been traveled. In particular, it includes the spaces for any obstacles, and the starting point.
The algorithm itself works by looping through and checking the open spaces and its neighbors. When it finds a good space, it will add that space into the closed list, and remove that space from the open list. Eventually, the algorithm will find its way to the end point, in which case, the loop will terminate and the shortest path will be found.

But how does A* find the “best” space?
It calculates it through simple formula :
F = G + H

G is the cost of moving to a certain square. For the sake of simplicity, imagine that we have a man on a 10 by 10 graph. For the same of simplicity, the man will only be allowed to walk in the four cardinal directions. Since all of the squares are equidistant from the next, all of the squares must have the same G cost. In this scenario, the G value for moving a single square can be any number, but in this case, we will set it to 1.

H is the heuristic. A heuristic is essentially a “guess” of the distance between the starting point and the end point. There are many ways to calculate the heuristic, such as the Manhattan Distance and the Euclidean Distance. In this tutorial, we will be covering the Manhattan Distance.

Manhattan Distance can be calculated by the following psuedocode :

function getHeuristic
  x = abs(startX - endX)
  y = abs(startY - endY)
  return minCostToMove * (x + y)

In our scenario, imagine that the man starts at the upper top left of the graph, at (0, 10). The end point is at (0, 0), at the very bottom left of the graph.
If we calculate the heuristic at the starting point, we find that our H value is 10. In other words, our man is at an absolute distance of 10 units away from the end point.

From here, there are two possible moves the man can make : downwards and to the right.

Now, we can put the formula stated above to good use.

Let’s consider moving to the right.

F_right = G + H
F_right = 1 + 11 = 12

If the man moves to the right, he will incur an F cost of 12.

But what happens if we move downwards?

F_left = G + H
F_left = 1 + 9 = 10

Since F_left < F_right, it can be concluded that moving to the right will take us farther away from the end point than moving downwards. As a result, the man will move downwards, since the F cost is lower for moving downwards.

If we repeat this over and over again, the man will eventually reach the end square by moving straight downwards. If the man moves in any other direction besides downwards, he will incur a higher F cost, since the H cost would increase if his absolute distance increased.

Terminate Conditions


A* will continuously run until one of the following conditions are met :

1. There are no more open spaces that can be traversed.
2. The shortest path to the end is found.

The only time the 1st scenario would happen is if there is no available path to the end. In this case, if the end point is impossible to reach, then there will be no shortest path available.

If you need a path-finding algorithm, particularly for graph traversal, A* is one of the many algorithms you can use.

Advertisements

Basic Multithreading in Java

Imagine that you have a sign-in system. However, for each sign-in, it takes half a second to complete. If ten people sign in, it would take five seconds to finish. For a hundred, it would take fifty seconds, and so forth. The run time would increase at a horribly fast rate if the sign-ins were processed one at a time.

But what if we wanted to process all of these sign-ins at the same time? We can solve this problem with multithreading. Multithreading is essentially the use of two or more threads at the same time in order to run a certain process concurrently.

(NOTE : this does not mean that an infinite number of sign-ins will all be processed in 0.5 seconds, as that requires an infinite number of processor cores.)

First, let’s create a dummy sign in class.

public class SignInRequest{
  public static void handleSignInRequest(){
    //insert magical logic here
  }
}

And then make a Request class using the Observer pattern, so that we can create a RequestListener afterwards.

Now, let’s create a new thread that we can run whenever we get a sign-in request.

public class SignInThread extends Thread{

  private SignInRequest request;

  public SignInThread(SignInRequest request){
    this.request = request;
  }
  public void run(){
    request.handleSignIn();
  }
}

At this point, we can use this SignInThread whenever we get a request.

public void onGetRequest(){
  SignInThread thread = new SignInThread();
  thread.start();
}

It is important that you run the start() method and not the run method.

By doing this, we can handle hundreds of sign in request concurrently, making the sign in process much faster.

In particular, threads are powerful when used with a computer with multiple cores.

For example, if you have 100 sign in requests, and multiple processor cores, you can split the sign ins between the cores by creating multiple threads. This means all of your cores can work at full-speed, whereas only one core would be used if it was not multithreaded.

However, you can multithread with a single core as well. However, when you only have one core, multithreading will not give any speed boosts, and it would be practically the same as if your code was single-threaded.

The most well-known use for multithreading is when you have a GUI. Consider a GUI program that calculates giant numbers. What happens if the calculation takes 30 seconds, and you decide to cancel the calculation? If the program only had a single-thread, this task would be impossible. The user cannot click the cancel button until the calculations are done. However, if it is multithreaded, then the calculations are completely separate from everything else. As a result, the user would be able to click the cancel button, since the calculations are done on a separate thread.

Multiple threads, with multiple cores, will cause your code to run much faster. Faster code, higher efficiency, and the ability to multitask. What’s not to like?

Sorting Lists with a Comparator

You receive a list of names, and you’re told to sort them alphabetically.

“Well, that should be easy!” you think. You can just iterate through the list and sort it with merge sort or quick sort.

But why go through all that effort, when you can just use a Comparator?

public void sortListAlphabetically(List list){
  Collections.sort(list, new Comparator(){
    @Override
    public int compare(String a, String b){
      return a.compareTo(b);
    }
  }
}

Collections.sort takes in two parameters : a List and a Comparator.

You can override Comparator‘s compare method and specify how the sorting will work. In this case, the compareTo method compares the first string with the second, alphabetically. It does this over and over again, comparing each String to the next (using merge sort) until the whole list becomes sorted alphabetically.

Of course, since a Comparator is a functional interface, meaning it only has one method, you can call it in a more elegant way via a lambda statement.

public void sortListAlphabetically(List<String> list){
  Collections.sort(list, (a, b) -> a.compareTo(b);
}

No @Override tags. No method names. No bloated code.
Just elegance and simplicity.

Nulls and Nulls and Nulls, Oh My!

As you’re typing away at your keyboard, creating new objects and methods, you realize something.

“Hey, what if this object is actually null?”

And so, you decide to cleverly check if the object is null, like so :


public void doStuff(Object object){
  if(object != null){
    //Work your magic on this object
  }
}

However, there are several problems with this approach. For instance, most programmers who use this technique do nothing if the object is null. This causes huge amounts of bugs and headaches for everyone.

In addition, null checking an object everywhere causes excessive bloating. In fact, most of these checks are unnecessary. You should not be checking if an object is null inside the main parts of your code. It is best to only check when data is first passed in.

An analogy for this is as follows :

A city, known for its wealth and prosperity, lies in the middle of a desert. Every one in the city is confirmed to be a good citizen, and crime rates are at an all-time low 0%. However, one day, a group of vandals approach the city. As they reach the outskirts, they are caught and kicked out. No criminals allowed!

The city continues to prosper for the rest of eternity.

However, a few dozen miles away, another city named Nullville exists. Unlike the other city, Nullville has no guards around the city. As a result, the city is flooded with nasty and evil people. To combat these evil-doers, Nullville decides to enforce a strict system of identification, with all good people getting an ID.

If you want to go outside, you need to show your ID. If you want to buy meat, you need to show your ID. If you want to go home, you need to show your ID. If you want to sleep, you need to show your ID. If you are caught without an ID, you are booted from Nullville, as you’re proven to be evil.

Clearly, Nullville is in a terrible situation. In order to do anything in Nullville, you first have to actually prove that you have an ID (proving that you’re != null). Even if you aren’t serial killer or a thief, you still have to prove that you have an ID.

As a result, like Nullville, programmers end up excessively checking their data for nulls, when it simply isn’t necessary. As in the first city, data should be checked on the outskirts of your code, not inside the main parts of it.

If you force functions on the “outskirts” of your code base to check for nulls, then you do not have to check for nulls in the core sections. The output is already guaranteed to not be null, so there is no reason, in the input of another function, to check for null.

In a nutshell, a contract needs to be made. Function A promises to return an object, but it isn’t null. Function B accepts an object, but trusts function A that the object will not be null. As a result, there is no reason for function B to check its input for null.

So don’t bloat your code. Check for nulls at the gates of your code, so that you don’t have to do it inside the code.