Posts Tagged ‘CIS 211’

Linked Lists and Patterns

I had trouble with this assignment. I was unsure of what classes we were supposed to be working with: there is List, ListI, ListC, EmptyList, Node, CollectionI. ListC does all the work for you, am I supposed to be using this class then? Well, I hope so, because that’s what I did. Anyways, I decided to implement the Observer, Visitor, and State patterns to work with the ListC and Node classes.

In order to fill my lists with Items, I needed to create an Item to store. I chose to create the Integer class, which implements Item, and is just a class that represents an integer. Therefore, I have lists of Integers, which for all purposes are just integers.

The Observer Pattern. I created a ListObserver that watches a ListC and announces when any Item is being removed from the ListC. Although the idea of having an Observer to be notified when a link is changed or broken is interesting, I had trouble deciding what data the Observer should care about. If a Node is added in the list, all the changed Nodes (the previous Node, the new Node, and the next Node) cannot be given to the Observer; that seems like it would require a big mess of conditionals and spaghetti code for the Observer to handle. The Observer would have to know which Node is now previous to the new Node and announce that. The Observer would have to know which Node is the new Node and announce that. The Observer would have to know which Node is now the next Node and announce that.

That seems too messy for a situation like this, so I just decided that the Observer would receive the Node that is being removed so it could announce “X Node/Item is being removed.” At first, the Observer called the toString() method on the received Node, but that would spit out some memory address or useless identifier. This information could be useful, but for our purposes I just decided to have the Observer spit out the toString() of the received Node’s Item, which in my project is an Integer. The toString() method of an Integer just returns an int.

So, when a Node is removed from a ListC, an Observer receives this Node and announces that Node.getItem().toString() is being removed.

The Visitor Pattern. I chose to create a ReplaceVisitor that is instantiated with 2 integers. The ReplaceV would then traverse through a given ListC and replace all instances of one integer with the other. This is where I was held up from my confusion on what classes we’re supposed to work with for this assignment. Since I was using the ListC class, when the get() method is called, it returns a List, but really that is just a Node. Anyways, the ReplaceV doesn’t mess with the actual Nodes that store the integer to replace, instead it just changes the value of the Item (Integer) that stores the integer that the ReplaceV is to replace. This works, but I would have liked for the ReplaceV to actually remove the entire Node and create a new Node with the different information, then stitch the new Node into the list. If this were the functionality, then the ReplaceV would cause the Observer to be notified.

The State Pattern. Once again, due to my confusion, I decided to implement this pattern into the Node class rather than the ListC class. To exemplify this pattern, I just create some new Nodes and manually stitched them together (rather than using the ListC class). The Node has 2 states: emptyState and fullState. The only method that is contained in these states is getItem(). When a Node has an Item in it, then it is in the fullState. When the Node does not have an Item, it is in the emptyState. When getItem() is invoked on a Node that is in the emptyState, a null is returned and a message is announced that the Node is empty and a null value was returned. When this method is invoked on a Node that is in the fullState, the Item is simply returned.

If the next of a node is set to some node that comes before it, that would form a cycle. How could that be detected? (note to say that node A is “before” B means there is a chain of one or more next pointers stepping from A to B).

Perhaps a DetectCycleVisitor could be used.  The DetectCycleVisitor would start at the beginning of the list and traverse the entire list.  In doing so, it could store every Node that it has been to and verify that its current Node is not one that it has been to already.  If this is true, then the DetectCycleVisitor could break from the recursion loop (which obviously is very important: if there is a cycle in the list, then recursion will continue infinitely) and return the Node that is referenced twice (its current Node).  I don’t have this coded up, but I imagine this could be doable, although storing every Node that the visitor has been to could be a costly process if the list is large enough, as well as having to iterate over all of them from start to finish every time it needs to check that it hasn’t already been to this Node.

This certainly would be a useful visitor though.  This could even work well with the Observer Pattern.  Every time a list changes, it notifies its Observers.  The DetectCycleVisitor could be an Observer, and when notified will tell the list to acceptVisitor(this).  Then, the visitor would traverse the list and look for any cycles that might have been created.  If this is true, the visitor will then announce this, or throw an exception, or somehow remove the cycle.  This is important because if there was a cycle and you did not send in a DetectCycleVisitor, then the next time you try and iterate over the list, an infinite loop will be created and the program will crash.

I think this sounds very cool actually, to use the Observer Pattern and Visitor Pattern together to thwart the possibility of containing cycles in a linked list.  Too bad I didn’t think of this before I did the assignment, I would have implemented this.

Categories: Assignments Tags:

The Lone Visitor

February 28, 2008 3 comments

The Visitor Pattern has some serious power. It’s just begging to be tossed into a data structure. Unfortunately, I don’t have much of any data structures going on other than some ArrayLists. But, powerful none the less.

I decided to use the Visitor Pattern for drawing my game entities to the screen. So, I created a Visitor interface declaring some visit() methods for all the entities in my game (Ship and Projectile). Then, I made a concrete class called Draw2DVisitor, which, as you may guess, draws things in 2D.

Prior to implementing this Visitor, the Ships and Projectiles had the capability to draw themselves. Although this works and is a common method, you’re stuck with graphics. What if for debugging purposes you wanted to skip graphics and instead print to the screen all the information about where your entities are located? Well if you provided an interface for all kinds of Visitors to use, you could simply create a PrintStringVisitor that printed this information to the screen. Amazing.

So after removing the draw capabilities from all entities and creating the Draw2DVisitor class, I implemented the Visitor into the game. Unfortunately, I quickly ran into a minor but annoying problem. Due to the design of my game loop, the graphics for the window are instantiated every iteration of the game loop, which means I have to provide this new graphics setting to the Draw2DVisitor so it knew where to draw the entities. Well, the only way the Visitor gets this information is through its constructor, which meant I had to declare a variable for the Visitor outside of the game loop, and instantiate a new Draw2DVisitor every iteration of the game loop, providing it the newly created graphics setting. This bothered me. I don’t need to be creating a new Visitor every iteration of the game loop, that’s a lot of unnecessary object creation! But I couldn’t see any way around it due to the already implemented graphics.

Singleton saves the day! Wait a minute. I don’t need any more than one Draw2DVisitor anyways since the single instance is passed around to every entity, why not make it a Singleton and restrict instantiation? Well, it turned out to fit nicely. I changed the Draw2DVisitor class to a Singleton, and provided a static method to retrieve the single instance of the Draw2DVisitor. Since the Draw2DVisitor needs a Graphics2D setting to draw to, I simply added this as a parameter into the static retrieve method. Now when the retrieve method is called, it sets its internal Graphics2D variable to the given parameter, and returns the single instance of the Draw2DVisitor.

Now, each iteration through the game loop, rather than instantiating a new Draw2DVisitor, a simple method is called to retrieve the single Draw2DVisitor and set the appropriate Graphics2D. Job well done Singleton.

Categories: Assignments Tags: ,

Four Patterns Demonstration

February 19, 2008 Leave a comment

I ended up writing so much in the accompanying email of the project file, I thought I’d put that here to describe the design.

The program simulates a teacher at school. A Teacher is created, and then Students are created and given a random favorite design pattern. The Students are then divided into classrooms, and the Teacher goes to each classroom and attempts to drill the design principle of the day into their minds. He then quizzes the Students afterwards on what and how he just taught them the design principle. The Students will not only remember what principle he taught them, but also his tone of voice as well as any manners that the he had.

Two things are randomized that alter the outcome of the program:

– Each Student’s single favorite pattern is chosen at random. This determines whether they will change State when the Teacher announces the pattern of the day.

– Each classroom is assigned random Students. Depending on the number of Students in the classroom whose favorite pattern matches the pattern the Teacher will be teaching (i.e. the number of Students who are paying attention), the State of the Teacher will change.

Let me explain where the 4 patterns are applied:

The Strategy Pattern – A Teacher has a SpeakBehavior (a certain tone) and this SpeakBehavior is determined by the State of the Teacher.

The Observer Pattern – When a Teacher enters a classroom, all the Students observe the Teacher. Then the Teacher announces the pattern of the day, and the Students remove themselves as an Observer from the Teacher if the announced pattern is not their favorite.

The Decorator Pattern – The SpeakBehavior classes may be randomly wrapped by a FunnyManner or WeirdManner.

The State Pattern – The State of the Teacher is determined by how many Students are observing it (paying attention). If the Teacher has already taught 2 classrooms today, and if the Teacher is not in a bad mood (bad state), then the Teacher will be in a Tired state. The State of the Teacher changes the SpeakBehavior of the Teacher, and may even decide (at random) to decorate the SpeakBehavior with a FunnyManner or WeirdManner.

Categories: Assignments Tags: ,

Recipe for Success: Implementing the State Pattern

February 14, 2008 Leave a comment

The State Pattern – Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.

Implementing the State Pattern:

  1. Fortunately, the State Pattern is a simple concept, and it’s uses are obvious. To implement the pattern in your project, you must first find something that may have various states. This is no complex task; a state is something as simple as Hungry, Tired, Angry, Alive, Dead, Sleeping, Attacking, Defending, Running, Walking, Stationary (Immobile), Waiting, etc. You want to make sure that whatever you choose has more than one state; if it only has one state, then it’s not really a state to begin with, but it’s rather the definition of what that object is.
  2. Now that you’ve found a Finite State Machine (something with multiple states), you need to decide explicitly what those various states will be. For example, you’ve decided a dog will be your FSM (Finite State Machine), then perhaps the states of the dog could be Hungry, Tired, Sleeping (quite a lazy dog).
  3. Now decide what within your FSM (our dog) changes depending on the state that it’s in. For example, if our Dog was in a Hungry state, it might look for food, but if it’s in a Tired state, it might look for a place to sleep. Usually you will be choosing methods that vary depending on the state. In this case, say there was only one method that varied depending on the state of the dog; what the dog’s looking for. The method signature might be: public void lookForSomething();. Now take this method signature and copy it (don’t erase it from the dog class).
  4. Now create a new hierarchy, either with an abstract base class or an interface, that declares (not defines) these methods — lookForSomething() — that you chose in step 3. This hierarchy will now be explicitly for use within your Dogs. If you have other animals that these states may apply to, you could use this hierarchy for them as well, but usually you will have a new hierarchy of states for each FSM that you have.
  5. Now, create subclasses within your State hierarchy that define each of the various states that your FSM will be using. In our example, you would create HungryState, TiredState, and SleepingState subclasses. Now each of these classes must define the abstract methods that were declared in the base class. You would write a definition in each subclass for the lookForSomething() method. In the HungryState, the method might tell the Dog to look for something to eat. In the TiredState, the method might tell the Dog to look for a place to sleep. In the SleepingState, the method might not do anything; you could just leave it blank. This is a viable option because as you know, if you’re sleeping you’re not going to look for something. Therefore, it is okay to leave the method definition blank in the SleepingState, or you might want to send output notifying the caller that the Dog is sleeping.
  6. You need to have an instance variable somewhere of the type of FSM that your states will be applied to. In our example, our abstract base class DogState would have a variable of type Dog. This is necessary for the various states so they have a Dog to change, otherwise they would just be definitions of methods that do something on their own, not change the way something acts. So, if you created your State hierarchy with an interface, you would have to add a variable of type Dog in each of the subclasses, but if you use an abstract class you could put that variable in the base class for every subclass to inherit.
  7. Now, within your FSM, you need to add some new member variables, one (or many) for each of the possible states, plus one for the current state. So in our Dog class, we would add four new variables of type State, and it would look something like this:
    • class Dog {
    • State hungryState;
    • State tiredState;
    • State sleepingState;
    • State currentState;
    • … }
  8. Now in the constructor of the Dog, you would create a new object of the various state subclasses, and assign those to the appropriate variables.
  9. Now, go back to your methods in the Dog class, in our case just the lookForSomething() method. Within this method, you just delegate the task of lookForSomething() to the currentState. The definition of the lookForSomething() in the Dog would look like: currentState.lookForSomething();. This will invoke the correct method definition depending on what state the Dog is in.
  10. When you make your checks on the Dogs hunger level and tired level, you would add an assignment to set the Dogs currentState = hungryState if its hunger level was low enough, or currentState = tiredState if it was tired enough.
  11. Now when lookForSomething() is called on the Dog, the task will be delegated to the currentState of the dog, and an appropriate execution of the method will occur. If currentState = tiredState, when lookForSomething() is called, the definition provided in the TiredState class will be executed.
Categories: Assignments Tags: ,

The Current State of Things

February 14, 2008 Leave a comment

The State Pattern is used far and wide throughout games. Two common uses for it apply to:

  1. The state of the game
  2. – Opening/Introduction
    – Main Menu
    – Loading
    – Running
    – Paused
    – Closing/Exiting

  3. The state of the units/characters
  4. – Damaged
    – Full
    – Upgraded

This is what I plan to implement into my game as well. I currently have a Game class, so I will add in a few States, particularly an OpeningState, a RunningState, and a ClosingState. As for my Ships, I will have the EnemyShips contain a DamagedState and a FullState, while the PlayerShip will contain a DamagedState, FullState, and UpgradedState.

So far I’ve not run into any problems. I’ve implemented the Ship states already and they’re working properly, but I haven’t started on the Game states. Although I’ve got the Ship states added, I don’t have any of the AI created in these states yet.

As for graphics, I’ve got them up and running, but I currently don’t have all the animations (frames) that I want implemented yet, and I haven’t found the BlasterBeam and Torpedo images that I want to use yet, so I have some images just for building purposes. I’ve got the PlayerShip movement and primary weapon fire methods added. They can be seen here:


Notice the jet on the Ship blasts out the back when it accelerates forward/up the screen, and goes away when not accelerating forward/up. I plan to add this same type of animation for the PlayerShip; when it flies to the left the ship leans left, and when it flies to the right the ship leans right.

Categories: Assignments Tags: ,

Recipe for Success: Implementing the Decorator Pattern

February 8, 2008 Leave a comment

Decorator Pattern – Attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality.

How to implement the Decorator Pattern:

  1. Take into consideration a class hierarchy, preferably one with many subclasses. The pattern applies very well when you have several features that a class of yours is comprised of. Rather than creating a subclass for every possible combination of these features, you want to create a Decorator for each individual feature. The Decorator must extend the class that it is going to be decorating, since a Decorator wraps itself around an object that it is decorating, and then stands in place of the decorated object. Therefore, the object and decorator must be of the same type. You can achieve this either through extending a class or implementing an interface.
  2. Now that you have a particular hierarchy that you want to change, you need to separate (but keep within the same hierarchy) your concrete classes from your decorator classes. For example, when you order a House Coffee with A Shot of Espresso and Whip Cream, your concrete class would be the House Coffee, and the Decorators would be A Shot of Espresso and Whip Cream. Remember, your Decorators must extend the same base class as your concrete classes.
  3. Within your new hierarchy, you should have a base class (Beverage), then a few concrete subclasses (HouseCoffee, DecafCoffee, etc…), and another abstract subclass as your decorator (BeverageDecorator). Within your abstract Decorator class, you need to include a member variable of type Beverage (whatever your base class is; whatever you want to decorate). When you decorate an object, that object is stored in this member variable. In the constructor for a Decorator, add a Beverage parameter, because when you construct a Decorator you must give it a Beverage to Decorate. Then, you should have all of your various features extending the Decorator class (BeverageDecorator). The features would be something like EspressoShot, WhipCream, etc.
  4. The idea of the Decorators is that they can modify the behaviors of the object they decorate. Using our example, each Decorator would add a cost to the total amount. After you’ve decorated your HouseCoffee with EspressoShot and WhipCream, when you call the cost() method of the Beverage, the call will pass through each decorator, where that decorator will add its own cost to the returning amount. Therefore, your Decorators must have a common functionality with your concrete classes (this should be implied since they all extend the same base class). If your Decorators do not, they probably shouldn’t be decorating the object.
  5. Now, to use the Decorators, it is simple. Here is an example:
Beverage beverage = new HouseCoffee();
beverage = new EspressoShot(beverage);
beverage = new WhipCream(beverage);
Categories: Assignments Tags: ,

problem = new DecoratorProblem (problem);

February 7, 2008 Leave a comment

The Decorator Pattern is fun. In my game, I’ve decided that every Ship will have a Weapon and a Shield. My “decorators” are the specific types (sub-classes) of Weapons and Shields, namely RailCannon and TorpedoCannon, and HeatShield and BlastShield, respectively. The idea is that I instantiate a Ship with the default Weapon and Shield, then decorate the Weapon and Shield with the decorators to give the Ship some kick. This allows for multiple decorators to stack onto the default weapon and shields, so if I wanted to upgrade the RailCannon, I could just decorate the weapon with another RailCannon. This just stacks a new RailCannon onto the weapon, so it doesn’t really upgrade the RailCannon, it just doubles the effects of the RailCannon.

Unfortunately with the Decorator Pattern, an object does not know what objects are decorating it, and there is no way to remove a decorator. I noticed this problem when considering the ammunition for my Weapons. Currently, each Weapon has an ammunition, and every time fire() method is called, an ammunition check is made. If the check passes (ammo > 0), then the Weapon fires and decrements its ammunition. The problem is that when the ammunition runs out (ammo == 0), there is no way to refill the ammo because I cannot target the specific decorator. This wouldn’t be much of a problem if I could just remove the empty weapon, and replace it with a new weapon with more ammunition (to simulate a reload), but there’s no way to remove a decorator.

The good news is that I smell another design pattern within this mess of Weapons, RailCannons, and Projectiles. I could very well see decoupling pattern fitting perfectly between these classes, but that is something that I would realize and implement later. Unfortunately, I demand a solution to the problem now. The current options seem to be removing specific weapon ammunitions, and just have a single ammunition count that each weapon decorator can add to. Although this would be easily implemented, it’s not really an ammunition count; it’s a ‘how-many-times-you-can-fire’ count. An example of the problem can be seen here:

  1. A Ship has 3 weapons and an “ammunition” count. Weapon a adds 60 to the ammunition, weapon b adds 30 to the ammunition, and weapon c adds 10 to the ammunition.
  2. This makes the ammunition count equal to 60+30+10 = 100.
  3. Every time the Ship fires, it reduces the ammunition count by the number of decorators, 100 – 3 = 97, since each weapon fired once.
  4. Do this many more times, say 12 more fire()’s. Here the problem occurs. The Ship has fired all its weapons 13 times, but the ammunition of weapon c was only 10, yet weapon c fired 13 times. Moreover, there is still 97 – (12 x 3) = 61 ammunitions left.

Obviously, this wouldn’t be a practical solution.

There also exists the easy-way-out solution of removing ammunition altogether and just allow Ships to fire() infinitely, or at least not be restricted by ammunition. If I chose this option, I would probably try and add a new restriction, like Temperature, that would limit how often a Weapon can be fired within a certain time.

Categories: Assignments Tags: ,