A Computer Science Blog

• Graphically interface the A* pathfinding code that I did in Java.
• MindFlex
• Flashcard Program
• A mini 3D game – using ORGE perhaps
• Improve F website.
• Start P website – load stuff on
• Make vid-tutes for P-website
• PHP image editing system

After losing 16 – 0 games to my brother in Starcraft, I’m feeling kind of frustrated. Still have not won a single one though a few have come close. BUT I have learnt some things you MUST DO in a multiplayer game of Starcraft if you’re going to be competetive in the least. I’m a Terran player so I’ll use Terran terminology.

• Do not stop building SCVs throughout the game. The exception is when you are having trouble spending all your money.
• Always keep an eye on expansion areas. Do not let the opponent take these. Use wraiths/Comsat to scout those areas.
• Keep harrassing your enemy to keep him on edge (hit and run). Wraiths are good for these (cloaked ones). If possible go for the economy. Most of all, go for unprotected expansions – usually ones that are just starting out.
• Keep good defense for ALL your expansions. Don’t leave them unprotected and expect they won’t be found. They will be. This means bunkers and siege tanks. Do not leave an expansion unprotected – it’s your opponent’s dream to see that. You expand to get more resources, not to lose them.
• Outproduce your enemy. This means building multiple factories/Starports etc.
• Research upgrades. Upgraded units are significantly more powerful. Not researching could mean a loss.
• Use Hotkeys on buildings and units. Hotkeys are not a nicety. They are central to the multiplayer game.
• When attacking, don’t think 1 group is enough. Have 3 or 4 groups of units assigned to Hotkeys and move them together. Thus you should have 36 to 48 units moving together.
• Repeat large attacks over and over until you win. The whole point is to build units at least as fast as you lose them, and keep moving them into an enemy location.
• Use Hold (H key) for defending units.

Comments?

mit unserem neuen Kunden - with our new customer

mit unseren neuen Kunden - with our new customers

der Kunde = the customer

die Kunden = the customers

The following is a personal note. Don’t try to understand it, if you come by it But if you want to figure what the hell it’s on about, go for it.

Persönliche Notizen. Versuchen Sie nicht, sie zu verstehen.

Note: move() contains the normalizing and actual adding of values to the currentPos. As long the object is moving, move() is called constantly. So, the process of normalisation keeps happening and the position values keeps changing.

def move(self, deltaTime): #If it collides with an entity then returns it, this is an internal function
startPos=self.graphic.pos
newPos=norm(self.dest-self.graphic.pos)*deltaTime*self.speed
roadKill=self.collisionTest()
if roadKill==None or self.graphic.pos==roadKill.graphic.pos:
self.graphic.pos+=newPos
#self.checkOutOfBounds()
else:
self.graphic.pos+=norm(self.graphic.pos-roadKill.graphic.pos)
#self.checkOutOfBounds()
return roadKill

if((self.graphic.pos.x>(self.dest.x-2)) and (self.graphic.pos.x<(self.dest.x+2)) and (self.graphic.pos.y>(self.dest.y-2)) and (self.graphic.pos.y<(self.dest.y+2))):
#print “arrived”
self.moving=false
if self.graphic.pos.x<0 or self.graphic.pos.x>99 or self.graphic.pos.y<0 or self.graphic.pos.y>99:
self.graphic.pos=startPos

public double[] normalise(int x, int y)

double[] normalised = this.divideVector(x, y, Math.sqrt(x*x + y*y));return normalised;

public double[] divideVector(int x, int y, double operand)

double newX = x / operand;

double[] theVector = new double[2];

return theVector;}

GRAPHS AND PATHFINDING

These are summarised from the Swinburne University of Technology AI For Games Lecture Notes. Hopefully it doesn’t infringe any copyright laws Fair use!

Introduction to Graphs

• Sets of nodes and edges
• Edges can be directed or not
• Edges can have costs or weights (not the same thing?)
• Trees are a type of graph.
• A “search tree” is where you get possible paths from a specific starting “root” node. In these search trees, nodes can be in multiple paths. The can’t be in the same branch though.
• Graphs can be described by their density –dense ones have lots of connections and sparse ones have few.
• Directed graphs (AKA diagraphs)
• A tree is a kind of graph with one path to each node. Links are always directed. Tree terms include – parent, children (ancestor, descendent (root, leaf))

Graph Representation
• Adjacency Matrix – a simple 2D structure with a Boolean or weight value in each cell to represent the connection
• Adjacency List – A list of each node and the nodes it is connected to. If a graph is sparse, this is a good choice because less memory is required to store this graph.

Graph Search Algorithms
• Uninformed Search
o A blind search. This ignores costs or other values that could help determine a better path.
o They don’t visit previously visited nodes.
o An example: DFS (depth first search). It is implemented using a LIFO stack of edges.
o Another example: BFS (breadth first search) – Spreads out uniformly from the start node. Grows exponentially in complexity . Not an optimal solution. Good when branching factor is low.

DFS – Uses LIFO STACK
Algorithm:
- WHILE nodes still in the stack:
 Remove the top edge from the stack
 Note the edges from the destination node
 Mark the edge start as visited
 Test for target found
 If not, add the edges with unvisited destinations to the stack.

BFS – Uses FIFO QUEUE (edges retrieved in the same order they were added in)
Algorithm:
- WHILE target not found:
 Remove the first edge and mark the parent of the edge as visited
 Note the edge parent and remove the edge from the queue
 Add all of the edges to unvisited destination nodes to the queue

Notes: BFS has a “fanning-out” behavior from the start node. This makes sure that the shortest path will be found.

Graph Search Algorithms – Dijkstra’s Algorithm

1. Start with the source node
2. Add edges that gives the shortest path from current source node to a node that’s not already on the SPT (shortest path tree)
3. Terminate when the target node is found

Graph Search Algorithms – Smoothing
Paths found can be jagged and unsmooth which looks bad in a game. Smoothing simply smooths out this path to make it look nicer. Could penalise points where there’s a change of direction.

Graph Search Algorithms – Collisions between Agents
• Need collision detection code – this is separate from graphs and searching.
• You can “discourage” the search algorithm to take a particular route where there are other units by adding a negative point where those units lie.

Tile-Based Navigation Graphs
• Popular simple approach where squares are used instead of nodes and connections – but same principle.
• Good starting point.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.”

- Edsger Dijkstra

That is not my opinion of course! But I’m intrigued by his view of VB . And I only just found out he said that, after studying his famous pathfinding algorithm at university!

Chinglish

http://www.spiegel.de/netzwelt/web/0,1518,487788,00.html

German newspaper Der Spiegel showcases some language treasures
Scroll down a bit and click on one of the 3 pictures to start the slideshow. Nebenwirkungen der Globalisierung – side effects of globalisation.

INFLUENCE MAPS 

Influence maps is a type of Tactical Analysis.

“…military influence is primarily a factor of the proximity of enemy units and bases and their relative military power.”

When working with IMs, think about the many small units (basic troops), signel air units (jet aircraft), anti-aircraft guns, combination of units.

Graphic representation of an influence map:

– Coming soon –

Calculating Influence

Types of influence drops-offs

• Linear drop-off
• Exponential
• More?

Three limiting approaches:

• Radius cut-off
• Convolution filters – used in image processing, can be used for a blurring effect
• Map Flooding – the influence value of a cell is the largest contributor only

Usage

• Use IM to determine safe areas on the map
• Plan attacks, guide movement (e.g. looking for weak points in the enemy line)
• Questions based on IM are known as IM Queries.

IM Queries

• What is the balance of power?
• Where’s the frontline?
• What’s the breakability of the enemy lines?
• Where are the weakest enemies?
• Am I being charged? Look for large drops in the IM.
• Where are the safe routes?

Also, take into account Fog Of War – which in this context, are the unexplored/unseeable areas. Fog Of War means a completely different thing in real life military planning.

The Law of Conservation means that energy is always conserved.

Transtional KE = 1/2mv^2

Rotational KE = 1/2I^2 

NOTE: ALL PHYSICS ENTIRES SO FAR HAVE SOURCED FROM http://tutor4physics.com/

Nice site.