One major courses for Computer Engineering (CPE) and Computer Science (CSC) majors at Cal Poly is the class CSC 102: Fundamentals of Computer Science. In this class we focused on the languages Python and Java. For our class project, my partner and I were to use Pygame and Processing to create a grid-based world simulation. The purpose of the project was an exercise in object-oriented programming, functional programming, and simple path-finding. You can view the sources for the project here for the Pygame version and here for the Processing version.

Project structure

The project was a large creation, but most of the code was written once and never touched again. The most important classes were the World class, the WorldView class, the actions, and the entity classes.

World and WorldView

The World class kept track of all the entities. It held a list of all entities and an ordered list of all events. It also managed moving entities around, calculating distances, and scheduling actions. The WorldView class was our Processing Main class. Every Processing applet requires a Main class to draw images to the screen and update itself periodically. WorldView handled image displaying, moving the viewport, key and mouse presses, and updating the World on a timer. Together the two kept the actions running on schedule and moved the entities about.

The Actions

There were four types of major functions in the Actions class: Action Creators, Entity Creators, Entity Schedulers, and Pathing Functions. The Action Creators would (as the name suggests) create actions. The actions were events executed at a scheduled time, and each action performed different operations based on their purpose: actions for moving entities would run the Pathing functions and actions for animation would cycle the sprite image. Some actions would schedule themselves again, thus creating looping actions (like animations). The Entity Creators would create their respective entities with various parameters and schedule their actions. The Entity Schedulers would run the respective Action creators and schedule those actions to run at specified times. The Pathing Functions would obtain the position of the target block (if any), calculate the best path, then move the entity one block in that path. Together, all the action functions created the dynamism of the project.

The Entities

There were multiple entities and multiple types of entities. In all, there were three abstract categories of entities and nine non-abstract, final entities. The full tree looked like the following (bold shows abstract type):

Entity:

• Blacksmith
• Obstacle
• Actor:
  • Ore
  • Vein
  • Animated:
    • Miner
    • OreBlob
    • Quake
    • Zombie
    • Birdie

Entity

At the head was the Entity class, which stored only the basic data each entity had: name, position, and sprite image. Non-abstract extenders of Entity were non-action classes. Blacksmith and Obstacle both extended Entity and both did nothing; Blacksmith was a target for Miners and Obstacle was the block of water that got in the way.

Actor

Under Entity was the abstract class of Actor. Actor stored data regarding the path from the pathfinding, the list of actions to be executed, and an arbitrary number for the speed of action execution. Ore had one action tied to it: an action to transform itself into an OreBlob. Vein had a repeated action to spawn ores in open spaces around itself.

Animated

Extending Actor was the abstract class Animated, which had an animation rate and a list of sprite images. Under Animated were Miner, OreBlob, Quake, Zombie, and Birdie. Miners roamed the world, seeking ores and picking them up. Whenever a miner was full, he would travel to the nearest Blacksmith and "drop the ores off". OreBlobs would spawn randomly from Ores that were not picked up and would seek out Veins and destroy them. Quake was an animated effect. Quakes were spawned whenever a Vein was destroyed, an OreBlob was killed, or a Birdie teleported out of the world. Zombies were what the Birdies transformed the Miners into. They would seek out OreBlobs and destroy them. Birdies were the birds that would teleport into the world to kill the Miners and transform them into Zombies. They could fly over everything except other birds, moved very quickly, and would periodically drop Ores.

Object-Oriented (OO) Programming

Java is a famous and ubiquitous OO language, and Python is a notorious scripting language with OO support. Using these two languages we were given different flavors of OO programming in similar contexts. For the first part of our project, our professor provided us with dirty and repetitive Python code. The code was of a Pygame project that simulated a small, grid-based world with various moving and interacting entities. The code was mostly functional: only a few classes existed. There were helper classes that were given to us (such as Point and Ordered_list) and the entity classes (which only held data and had no behavior for themselves).

Step One: From Functional to OO

Our first task was to move appropriate functionality into classes. The behaviors of all the entities were defined by general external functions. Without using inheritance, we were to copy each relevant function into associated classes as methods. 'No inheritance' meant there were multiple copies of methods that all did the same thing; this was intended to show the benefits of inheritance when we apply it. There were also numerous functions for the world that had to be moved. In addition to moving all the functions over, we also had to change the method calls in the rest of the code to make it run. This exercise was intended to introduce us to defining object methods and accessing them.

Step Two: From Prototype to Inherited

After increasing the sizes of our projects tenfold, we were allowed to use inheritance. Using Python's odd system of inheritance, we grouped like entities together under their shared parent classes. This short exercise was to introduce Python's system of inheritance. Like other OO languages (like Java), Python uses the super keyword to reference the parent class, the only difference is that you need to be explicit with a super call. In Java, super refers to the super class and will implicitly cast-up the object in question by performing operations defined in the super class. In Python, super is somewhat magical. On its own it is a function that will return an object of type super that has a reference to the parent class(es) of a class. When invoked, the super object will call the method of the parent class, passing in the object in question. The beauty of using super as opposed to directly calling the parent class is that super also manages multiple inheritance for you.

Step Three: From Python to Java

At this stage we started moving the objects over into Java. Primarily we focused on moving the entity classes and the World class. We were then to test our migration by writing endless test cases to ensure everything moved correctly. The test cases simulated a world with entities, without displaying it. This was an introduction to Java's flavor of OO.

Step Four: From Pygame to Processing

After moving just the entities and the World into Java, we had to move in everything else: the world view, entity actions, and keyboard interactions. This version used Processing to display the world to the screen and manage the keyboard interactions (using arrow keys to move the view port, pressing space to pause, etc). The difficult part was moving over the actions. This part of the assignment proved to be rather challenging for one reason: Java is not functional. Python is functional, so functions are first-class and could be returned and passed around easily. However, in Java we needed to use the new Function interface to translate the Action code over.

Step Five: From Here to There

Once everything on the Java side was behaving like everything on the Python side, we were to change the entity pathfinding. The entities that moved had a very simple system: horizontally first, then if it can't go any more horizontally (in the same column or obstructed) go vertically, then if it can't go vertically (at the destination or obstructed) either celebrate victory or admit defeat. This system resulted in numerous "trapped" entities, even if there may be another way to get to their destination. For that we were introduced to A* pathfinding. A* works by calculating the "cost" to visit a node and comparing costs over a large collection of visited nodes to find the least costly path.

Step Six: From Idea to Reality

All of the previous steps were guided by our professor. For this part, however, he handed the reigns to us to add our own modifications. The changes we implemented had to be triggered by a mouse-click anywhere in the world and had to follow a few rules:

1. there must be a visual change to the area near the mouse-click
2. there must be a new type of entity to spawn in the world
3. there must be an existing entity that will be affected (in appearance and behavior) in some way

For our creative addition, my partner and I added a portal to an alternate dimension. When you click the world, a portal opens, showing its presence by inverting the colors of all entities and background tiles in the portal region. Killer birds travel through the portal and spawn in the world, fly around the map, and attack miners. The attacked miners turn into zombies and roam about chasing ore-blobs and turning them into veins.

Functional Programming

Python is a multifaceted scripting language. Besides OO programming, it is rather powerful in functional programming. Java, however, is not. Java is the staunch OO language and has been since the beginning of time, but the team at Oracle has been slowly adapting to the changing styles of programming. In Java 8, one can now use "lambda expressions", which are (in Java) a way to define a class without needing a full, formal definition. Lambdas open the possibilities of the functional paradigm as API users are able to specify operations to perform. Also new in Java 8 is the Function interface, which contains various types of functions: predicates (return true or false), consumers (return void), operators (return same type as argument), and more. Each of these functions aren't really functions but objects with one calling method, like Ruby's proc objects with the call method.

Between Python and Java, functions in Python are more powerful and easy to use than their counterparts in Java. For one, functions in Python are first-class citizens, so they can be passed around, stored to variables, and even created and called in-line. Functions can also be created in closures (the coolest thing in programming), called recursively (also the coolest thing in programming), even created in closures and called recursively (the coolest thing in programming squared). Variables do not need to be instantiated for the code to compile, so functions can reference themselves, even though they technically do not fully exist at compile-time.

In Java, on the other hand, functions are not as privileged. Functions are wrapped in objects, so, similar to Python, they can be passed around and stored to variables as usual. However, functions cannot be created and called in-line easily, nor called recursively in a succinct manner. Java has strict rules for variables and requires all variables be instantiated (assigned to a value, even null) to compile. Because a function object is not considered instantiated until the entire function is compiled, any references to itself inside the function code will be references to an uninstantiated variable. You may think you could set the function to null first, then define it: technically it will be instantiated when you reference it in the function definition. This, unfortunately, doesn't work since all local variables referred to in a function must be treated as final, and changing the value of the variable pointing to your function violates that rule. Fortunately, there are numerous other ways to get around the compiler police.

One method my professor taught us was to wrap the recursive-function-to-be in an array of length 1, like so: IntUnaryOperator[] fact = new IntUnaryOperator[1]; or IntUnaryOperator[] fact = { null };. Then, any time you need to reference the function, refer to it as element 0 of that array: fact[0]. This works because Java has more lenient rules with arrays simply because they are much more difficult to check and track all the values, so the compiler doesn't bother. Even though element 0 of that array is not treated as final, Java doesn't check that it follows the rules since it's in an array, providing an inconvenient, but effective, exploit to defining recursive functions.

In the context of the project, the Action code was the only functional code. In Python, the action code was easy to use because functions in Python can be called recursively, which is what was required for the actions to reschedule themselves. In Java, the action code was more difficult to write because functions cannot be called recursively easily. After implementing the exploit our professor taught us, the action code became easier to write.

Pathfinding

Depth-First Search

During class we learned briefly about graph theory and path finding. To introduce us to the topic, our professor demonstrated the Depth-First Search algorithm (DFS). DFS works by traversing a grid in a predetermined order without visiting the same node twice and "falling back" a node if there are no available paths to take: it goes as far as it can without overlapping before having to backtrack. Think about the common strategy to solve a maze by walking along the left wall and having to go back only when there's nowhere else to go. Given that there is a path between A and B, DFS is a fail-proof algorithm that will find a path from A to B. The problem with DFS is that it is not a heuristic, meaning that it is brute-force and not methodical. Though DFS will find a path, that path may not be the best path; in some cases, it may be one of the worst paths possible. The following is a vastly over-simplified example of how DFS works in the context of the project:

a SPACE is legal if
   the SPACE is in the grid and
   the SPACE has not been visited and
   the SPACE is not an obstruction

Loop until done
   if I am at the target then
      celebrate and break Loop

   else if all spaces are visited then
      error: no path to target

   else if RIGHT is a legal space then
      go RIGHT and mark it as visited

   else if UP is a legal space then
      go UP and mark it as visited

   else if LEFT is a legal space then
      go LEFT and mark it as visited

   else if DOWN is a legal space then
      go DOWN and mark it as visited

   else if NONE are legal spaces then
      go BACK

This pseudo-code demonstrates how one can reach their target by using the pattern RIGHT-UP-LEFT-DOWN. DFS is better written recursively, but the recursive definition is a bit more programmy instead of englishy. It is a rigid algorithm, so the order in which it traverses is predetermined: if all you needed was to go DOWN to get to the goal, DFS would make you go RIGHT, UP, and LEFT first. It can be made more heuristically, determining its search order for every node, but that just complicates things.

A* Pathfinding

In the project, rather than using DFS we were encouraged to use A* Pathfinding. A* is a heuristic search algorithm that attempts to follow the path of least resistance from the start point to the finish point. A* calculates the "cost" of each node and proceeds along the path of the lowest cost. I'm throwing the word "cost" around without proper explanation, but think of the cost to get to a node is the amount of energy required to get there. For example, the cost to get to a node through water could be greater than to go by land since swimming is more exhaustive than walking. The cost of a node is calculated as Cost = PathCost + Heuristic where PathCost is the total cost to reach that node from the start and Heuristic is the estimated cost to get to the finish from that node. The value of PathCost is calculated by adding up all the costs spent to get to this node. The value of Heuristic is estimated using a variety of techniques: for a grid-based world where actors can move only once block at a time (up, down, left, or right), then a reasonable heuristic would be the taxicab distance from the current node to the finish node. The estimated heuristic should never overestimate the actual cost to get to the finish: overestimates undermine the effectiveness of the algorithm. Often the cost equation is written as f(n) = g(n) + h(n) where f is Cost, g is PathCost, and h is Heuristic, but I prefer to write the variables in English for explanation purposes.

The process behind A* is interesting; it seems complex, but once you understand it, it seems so obvious. The following is an overview of how the algorithm works in the context of the project both with a pseudocode example and English explanation. Assume that each node keeps track of three values: its PathCost value, its Cost value, and the Node from which it was entered. Because the model is using a simple grid in which only the four cardinal directions are allowed, the Heuristic value for each node stays constant (the nodes don't move about, so the Heuristic is the distance from the Node to the Goal) so assume all Heuristic values are known by each Node. CalculateCost for Node is defined as Node.PathCost + Node.Heuristic.

ClosedSet = {}
OpenSet = {StartNode}

StartNode.PathCost = 0
CalculateCost for StartNode

while OpenSet is not empty
   CurrentNode = Node in OpenSet with lowest Cost
   remove CurrentNode from OpenSet
   add CurrentNode to ClosedSet

   if CurrentNode is Goal
      celebrate and return the Path traveled

   for Neighbor in CurrentNode.neighbors
      if Neighbor in ClosedSet or Neighbor not valid
         ignore and continue

      CurrentPathCost = CurrentNode.PathCost + 1

      if Neighbor not in OpenSet or CurrentPathCost < Neighbor.PathCost
         Neighbor.CameFrom = CurrentNode

         Neighbor.PathCost = CurrentPathCost
         CalculateCost for Neighbor

         add Neighbor to OpenSet if not Neighbor in OpenSet

error: no path to Goal

First, you declare two sets: OpenSet and ClosedSet. OpenSet is for nodes waiting to be evaluated; this will contain only the Start node at the beginning. ClosedSet is for nodes that have already been evaluated and won't be considered again; this will be empty at the beginning. While there are nodes in OpenSet, repeat the following steps. Remove the node from OpenSet with the lowest Cost and refer to that node as CurrentNode. If CurrentNode is the goal, celebrate and and return the path travelled by following the CameFrom values for each Node. If not, then for every Neighbor around CurrentNode, do the following. If Neighbor is in ClosedSet (we have already visited it) or not a valid location to visit (we can never visit it) then ignore it and continue with the next Neighbor. Store the current PathCost to the variable CurrentPathCost. If the Neighbor is not yet in OpenSet, or (if it is) if the CurrentPathCost is less than a previously established PathCost for Neighbor, then set the CameFrom node for Neighbor to CurrentNode, set the PathCost to CurrentPathCost, update Cost for Neighbor, and add Neighbor to OpenSet if it is not already in OpenSet. After going through every neighbor, repeat the while loop until there are no more Nodes left in OpenSet. If after all nodes have been visited and there is not a single path to the goal, error out and complain.