jump to navigation

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 :)

Flash resource June 3, 2007

Posted by deltawing in Programming.
1 comment so far

www.gotoandplay.it

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:

  1. Add start-node to the open list. REPEAT FOLLOWING:
  2. Look in the open list. Which has lowest estimated total cost value? This becomes your current node.
  3. Remove the current node from the open list and add it to the closed list.
  4. FOR all outgoing connections from this current node:
    1. IF NOT passable OR on closed list, THEN ignore
    2. IF NOT in open list, ADD to open list. Make the current node the parent of this node.
    3. 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.
  5. 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)
  6. 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.
  7. Reverse the list.
  8. 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?

Event handling in Java December 19, 2006

Posted by deltawing in Java, Programming.
1 comment so far

Event handling has always confused me. So I’m going to summarise it all here.

//Handling mouse events
public boolean mouseDown (Event e, int x, int y)
{
//code here

    return true;

}

- what is an Actionlistener why is it needed?
- MouseListener? why is it needed

-actionPerformed? getSrc?

If there are several buttons, textfields, etc that need to be handled, use actionPerformed(ActionEvent e)
public void actionPerformed (ActionEvent event) {

String cmd = event.getActionCommand ();

if ( cmd.equals (“A”)){
fPushACount++;
showStatus (event.getActionCommand () +
” pushed ” + fPushACount + ” times”);
}else{
fPushBCount++;
showStatus (event.getActionCommand () +
” pushed ” + fPushBCount + ” times”);
}

} // actionPerformed()

Don’t forget to attach the listeners to the event source (ie buttons or else it wont work)!!