End of the Blog August 28, 2007
Posted by deltawing in Computer Science, Internet.add a comment
Well, it’s the end of this blog. I’ve moved to www.j7labs.com
No furthur updates will be made here.
My Pathetic Excuse for a Computer August 3, 2007
Posted by deltawing in Computer Science.add a comment
I think from now on I need a weekly “bitch session” just to release my frustrations 
Let’s see what I have for a computer …
1.6 ghz CELERON
256mb of RAM
Integrated video card
and these are the software I need to use (most of the time I need more than 1 app open)
3dsmax 9
Photoshop CS3
Flash CS3
Dreamweaver CS3
UnrealTournament 2004 (for testing UnrealScript)
Visual C++ Express 2005
Eclipse
Did I mention this was a laptop? And when I pick it up I can hear loose bolts inside. Arghhh. I can almost hear the CPU screaming “no!!! i can’t do this anymore!!”.
And it doesn’t help that my last attempt at a job (a waiter), ended up with me being let go in 3 days. Apparently I had no experience and they wanted experienced and quick waiters. So really…having no job doesn’t help me in getting a new Core 2 Duo.
Of course…I could always go to the university to use the computers in the library. Although they are currently having a chronic virus infestation problem which means the computers their run just as slow as my laptop. It’s also nice that whenever I plug my USB stick into any of the computers in the library, a virus automatically gets uploaded onto my stick.
I suppose I could use the family desktop (which is a 1.6ghz P4 with 512mb ram) , jury-rigged with a new video card, which is actually considered low end, but still better than the one that came with the computer. Great, only if I had access to it
Well, it’s time to start looking for a job again.
Artificial Intelligence – Goal Oriented Behaviour June 4, 2007
Posted by deltawing in Computer Science, Games, Programming.add a comment
The AI must have goals if it’s to achieve something. Each goal is assigned a priority. At each game tick, the AI considers the situation in the world and extrapolates from that, what to do. E.g. if its based is under heavy attack, it would need to defend it, instead of trying to expand elsewhere.
So what happens is a character has a goal or motive, and can choose from a set of actions. It chooses the action that best fulfills the motive. There’s a complication – choosing an action can have consequences. E.g. in an RTS the computer might want to build a fleet of air units that specialise in attacking other air units, to fend off the enemy’s air presence. This seems like a good idea to a problem. However, this game air units are hugely expensive and the construction will lead to a resource problem. With this deficit how can the computer build other defenses? Can the computer find another action that won’t have such large consequences. Perhaps they could build cheaper, but less effective, ground to air units.
Here is some pseudocode copied from a page of Swinburne University lecture notes, which was probably copied from Ian Millington’s AI For Games Books:
def chooseAction(actions, goals):
# find the lowest discontentment action
bestAction = actions[0]
bestValue = calcDiscontent(actions[0], goals)
for action in actions:
thisValue = calcDiscontent(action, goals)
if thisValue > bestValue:
bestValue = thisValue
bestAction = action
# provide the action we found
return bestAction
class Goal:
value
def getDiscontent(newValue):
return newValue * newValue
def calcDiscontent(action, goals):
# keep the running total of discontent
discontent = 0
# total up the value change for each goal of this action
for goal in action.goals:
newValue = goal.value + action.getGoalChange(goal)
discontent += goal.getDiscontent(newValue)
return discontent
Oh by the way, I was just playing Starcraft (practising for Starcraft 2), and I noticed something. Sometimes when I’m approaching the enemy base, the Zerglings will try to both attack me and run back to defend its base at the same time. They want to do both equally. So, what happens is they can’t decide and just run toward me, then back towards the base, and then towards me again – in a constant loop 
The A* Pathfinding Algorithm Personal Notes and Pseudocode May 31, 2007
Posted by deltawing in Computer Science, Programming.add a comment
These are personal notes. If they don’t make sense to you, that’s because they probably shouldn’t. If you can make sense of it, you are a genious!!
Graph
A graph has nodes and connections.
Nodes (pn: NodeRecord)
A node is like a waypoint. It knows and stores its heuristic value, cost so far, and estimated total cost.
note: Cost so far is the cost so far from the start to this current node we’re on. Estimated total cost is cost so far + heuristic value.
Estimated total cost = Cost so far + Heuristic value
F = G+H (from other text book – same thing)
Connections (or Edges)
Connections connect nodes together. Connections have costs which is generally the distance.
Heuristic
The heuristic can be implemented as a class. Has a method that returns the heuristic value. Use integer?
Notes in dot point:
- Pretty much the same as Dijkstra’s algorithm, just with a heuristic.
- A heuristic in this context is a guess of the estimated cost from the |current| node to the |target node|. The most well known and simple is perhaps the Euclid heuristic, which is just the “as the crow flies” distance from the |current node| to the |target node|. Problems – can underestimate distance esp. indoors.
- Implemented in a loop (double loop – a while and a for). You iterate through nodes.
- Need a list to store open and closed nodes.
- Simplest implementation of a graph for A* pathfinding would be grid-based. Then you have just diagonal, vertical and horizontal connections. All diag. lengths are the same, and all vert. and horiz. ones are the same length.
- G and F need recalculating along the way.
- Instead of having a node “pointing” to its parent node, just have a LIST of the route so far? Both ways are fine. (Millington/Lester)
A* Pathfinding Steps:
- Add start-node to the open list. REPEAT FOLLOWING:
- Look in the open list. Which has lowest estimated total cost value? This becomes your current node.
- Remove the current node from the open list and add it to the closed list.
- FOR all outgoing connections from this current node:
- IF NOT passable OR on closed list, THEN ignore
- IF NOT in open list, ADD to open list. Make the current node the parent of this node.
- IF in open list already, check to see if the path to that node has a smaller cost-so-far. If so, that’s a better path. So make the current node the parent of this node.
- STOP if target node is added to the closed list (i.e. path found) OR open list has nothing in it anymore (i.e. no path found)
- Get the path either by using the parent node method, or you would have a list with the path in it by the time you get to the target.
- Reverse the list.
- Finish: You now have a list with the nodes in correct order, from start to target.
To graphically represent this, use draw a simple grid. The movers are just circles that move from one node to another. Or simply just draw the path as a line from node to node (i.e center of square to center of sqaure). Language: Java. Reason: Familiar/Solid language.
The movers will need to have steering behaviours (and to avoid each other if there are multiple movers). The main thing however, is to get the mover to seek from node to node. The seeking will cause abrupt changes in the mover’s path. How to fix?
Essence of OOP September 13, 2006
Posted by deltawing in Computer Science.add a comment
For those confused, a simple breakdown of the OOP concept:
- Encapsulation – the hiding of information
- Inheritance – a class extends another class
- Polymorphism – several methods have the same name, or, several methods have the same name but different parameters. Overriding Vs. Overloading.
Misc:
Overriding Vs. Overloading
Overriding methods where you have the same arguments for the overriding method, as opposed to overloading where you have different arguments. ?Overriding used with inheritance?
Reference:
http://www.developer.com/tech/article.php/974871
Algorithms and Efficiency Part I September 5, 2006
Posted by deltawing in Computer Science.add a comment
How do you measure the complexity and efficiency of code? This is a summary of what I learnt in my lecture notes. Imagine you are searching for a name in a phone directory. You can do this in 2 ways:
- Linear search – you flip through the phone book from the first page to the last, looking for the name.
- Binary search – you open a book in the middle and start from there. If the name you are looking for alphabetically precedes the current alphabetical index, then from now on ignore the entire right hand side of the phone book. Then, you simply repeat the process for the remaining left hand side of the book and so on until the name is found.
With linear search, the average time that it will take to search the directory is expressed by (n / 2) t, and n * t is the worst case, where n is the number of names in the directory and t is time that is needed to read each name.
With binary search, the worst case time that it wil take to search the directory is expressed by (Log₂n + 1) t
Assuming that it takes 1 second to look at and compare a name in the phone book, let us compare these 2 methods:
Linear Search
To search through 3 million names, it will take a linear search on average 17.36 days to find the name.
Binary Search
To search through 3 million names, it will take a binary search no longer than 21.52 seconds to find the name.
To be continued.
Stacks, and how they work August 26, 2006
Posted by deltawing in Computer Science.add a comment
What is a Stack? It is a type of data structure. Just think of a deck of playing cards or a pile of bricks. With a Stack, you must follow LIFO (Last-In-First-Out). This means that if you stack a pile of bricks and want to take one off, you must take the one at the top, i.e. the last one you put on. With this example it’s probably better to say (Last-On-First-Off), but then that wouldn’t be proper terminology . Anyway, just think of each brick as an object and there you have it.
Stacks have the functions push and pop. Push means that an element is added to the top of the Stack, and Pop means an element is taken off the top of the stack and the element returned. If you want to see an element without popping it, just use the peek function. You can’t remove or insert elements from the middle of a Stack.
Stacks are useful for applications such as calculators that use Reverse Polish Notation (RPN).
For instance, take the familiar expression 8 * (5+4). This is translated to RPN as 5 4 + 8 *
Read the RPN from left to right.
- push 5 onto the Stack
- push 4 onto the Stack
- Hah I see a + sign! Therefore now I add 5 and 4 and then push 9 onto the Stack.
- push 8 onto the stack. (ok a little update we now have 9 and 8 on the Stack.
- There is a * sign! Therefore now I multiply the last 2 items on the stack which is 9 and 8.
- We come to a grand total of 72
Also you can check Palindromes with Stacks too. The idea is that you add items to the Stack and when you remove them one by one you get them in the reverse order that you put them on. Now all you need to do is compare to see if they are the same.
Stacks can be implemented in several ways with Java – Vectors, ArrayLists and LinkedLists:
Example of a LinkedList August 23, 2006
Posted by deltawing in Computer Science, Java.2 comments
Here is a very simple example of a LinkedList to get started with:
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
public class LinkedListTest
{
public static void main(String[] args)
{
//create a new LinkedList
List list = new LinkedList();
//adding elements to the list. We are adding Strings.
list.add(“i”);
list.add(“like”);
list.add(“to”);
list.add(“code with”);
list.add(“Java 5″);
//the list object calls the iterator() method of the LinkedList to obtain the iterator
Iterator iter = list.iterator();
while(iter.hasNext())
{
System.out.println(iter.next());
}
}
}
—————————————————————————————–
LinkedLists are:
- Very efficient for inserting and removing elements.
- Not so fast when accessing elements in order (though not slower than a normal ArrayList)
- Slow when randomly accessing elements
- Java 1.5 version supports Autboxing
- Uses an Iterator object to traverse through the elements
- Comes in more flavours – Doubley Linked Lists and Circular Linked Lists.
Please, corrections if mistakes have been made!
