I need help with my game...

[Xxspade13xX]

Me and some of my friends are making a game like empire earth or starcraft/warcraft. The biggest problem that we are having is trying to get any object to move where the mouse clicks. Any basic code will help, just need an object to take the shortest route to the location of the click. Also how would you make a mini map? We need one that will show where the enemies are in relation to the real map. The objects would have to move proportionately to the objects on the large map. Any help would be greatly appreciated. Thanks in advanced.

[pingnak]

Although A* (A-star) is all the fad, I still like Dijkstra's algorithm (look it up). I think many don't use it only because they can't say it or spell it.

Basically, it's a seed fill from the destination (or origin) of the path that writes into a map 1+the value of the previous map location it popped for the next search. What you do when following the path is look at the map locations around you and see which one has a lower number, and go thataway.

http://www.google.com/search?q=Dijkstra
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

It has several very useful properties:

Simple to implement
Quick if you don't go overboard with too big a map
One fill can generate the path for many characters
It can be implemented trivially with an Array (for the FIFO) and a BitmapData (for the map)
It handles 'difficult' terrain - you can add values into the map that are 'harder' than others, like swamps, mountains, etc. and the path behaves accordingly

[pingnak]

This implements a version of Dijkstra's Algorithm in BitmapData and a little interactive test toy interface. It's written in Actionscript 3 and can be built with the Free Adobe Flex SDK, as is. I whacked it together today because I needed it anyway.

mxmlc Main.as
I tested it to make sure it does build.

Or, you can use the attached zip file which has the original source before it was chewed up by the preprocessor. That should make certain things clearer. You'll need the preprocessor tools mentioned in the README.txt for that to build it.

Of course, once you have all of this, your AI work isn't finished. You have to be able to creatively 'cripple' the routing so it's not so omniscient, and control just how much routing it does, and add handling for difficult terrain and other such goodies.

mylib/Dijkstra.as


// Implement FIFO based on singly linked list of X,Y objects
// This one winds up with a 'corrupt' state when the last one
// is out, but it doesn't have to check the tail pointer
// every time something's added, either.

// The data we store in the map is actually backwards.
// Normally, it's 0->max, but since 0 is 'outside', we'll go max->0
// The 'impassible' value is 0
// Values above 'UNFILLED' value are not filled
// Anything above UNFILLED_VAL is treated as 'difficulty'

package mylib
{
import flash.utils.ByteArray;
import flash.utils.getTimer; // Define things common preprocessor directives want.
import flash.display.BitmapData;
import flash.geom.Point;
import flash.geom.Rectangle;

public class Dijkstra
{
/** The map we to the calculations based on */
public var template:BitmapData;

public function Dijkstra( temp:BitmapData )
{
template = temp;
}

/**
* Make a bitmap suitable to path using the map's template
* @return A BitmapData identical to the template
**/
final public function CloneTemplate():BitmapData
{
return template.clone();
}

/**
* Make a bitmap suitable to path using the map's template
* @param Bitmap of same size to receive image
* @return The bitmap passed in
**/
final public function CopyTemplate( bitmap:BitmapData ):BitmapData
{
bitmap.lock();
bitmap.copyPixels( template, bitmap.rect, new Point( 0, 0 ) );
bitmap.unlock();
return bitmap;
}

/**
* Do the flood Fill starting at {x,y} with no source to stop it
* You wind up with a map from all points on the map to the destination
* @param pathmap Bitmap already filled with the map template
* @param dx,dy The target
* @param sx,sy Optional origin to terminate the search if it's incountered
**/
final public function Fill( pathmap:BitmapData, dx:int, dy:int, sx:int = -10, sy: int = -10 ):void
{
/* Make sure the fill will have something like a finish */
var value:uint;
value = pathmap.getPixel( dx, dy );
if ( !( ( value ) >= 0xffffff ) )
return;
pathmap.setPixel( dx, dy, value - 1 );
pathmap.lock();
var headstack:Object = null;
var tailstack:Object = null;
{
tailstack = headstack = {x: dx, y: dy, next:null};
}
var curr:Object;
var newvalue:uint;
var x:int;
var y:int;
var tx:int;
var ty:int;

while ( null != ( curr = headstack ) )
{
x = curr.x;
y = curr.y;
if ( x == sx && y == sy )
break;
value = pathmap.getPixel( x, y ) - 1;
tx = x + 1;
ty = y;
newvalue = pathmap.getPixel( tx, ty );
if ( ( ( newvalue ) >= 0xffffff ) )
{
pathmap.setPixel( tx, ty, value );
{
tailstack = tailstack.next = {x: tx, y: ty, next:null};
}
}
tx = x;
ty = y - 1;
newvalue = pathmap.getPixel( tx, ty );
if ( ( ( newvalue ) >= 0xffffff ) )
{
pathmap.setPixel( tx, ty, value );
{
tailstack = tailstack.next = {x: tx, y: ty, next:null};
}
}
tx = x - 1;
ty = y;
newvalue = pathmap.getPixel( tx, ty );
if ( ( ( newvalue ) >= 0xffffff ) )
{
pathmap.setPixel( tx, ty, value );
{
tailstack = tailstack.next = {x: tx, y: ty, next:null};
}
}
tx = x;
ty = y + 1;
newvalue = pathmap.getPixel( tx, ty );
if ( ( ( newvalue ) >= 0xffffff ) )
{
pathmap.setPixel( tx, ty, value );
{
tailstack = tailstack.next = { x: tx, y: ty, next:null}
}
}
{
headstack = headstack.next;
}
}
pathmap.unlock();
}

/**
* Use the results of a fill to find a Path
* @param pathmap Bitmap already filled with the map template
* @param dx,dy The target
* @param sx,sy Starting point
* @return A list of waypoints or an empty list if the destination is unreachable
**/
final public function Path( pathmap:BitmapData, dx:int, dy:int, sx:int, sy:int ):Array
{
// See if we're going to crap out, and stop accordingly
var result:Array =[];
var value:uint;
value = pathmap.getPixel( sx, sy );
if ( ( ( value ) >= 0xffffff ) || value == 0 )
return result;

var best:uint;
var bestx:uint;
var besty:uint;
var bestdx:int;
var bestdy:int;
var x:int = sx;
var y:int = sy;
var tx:int;
var ty:int;
var dirxLast:int = 0;
var diryLast:int = 0;

// Add the starting point
result.push({x: sx, y:sy});

// Check each neighbor, find the nearer of the set, use that as the next point
while ( x != dx || y != dy )
{
best = pathmap.getPixel( x, y );

tx = x + +1;
ty = y + 0;
value = pathmap.getPixel( tx, ty );
if ( ( ( value ) < 0xffffff ) && value > best )
{
best = value;
bestx = tx;
besty = ty;
bestdx = +1;
bestdy = 0;
} // Right
tx = x + 0;
ty = y + -1;
value = pathmap.getPixel( tx, ty );
if ( ( ( value ) < 0xffffff ) && value > best )
{
best = value;
bestx = tx;
besty = ty;
bestdx = 0;
bestdy = -1;
} // Up
tx = x + -1;
ty = y + 0;
value = pathmap.getPixel( tx, ty );
if ( ( ( value ) < 0xffffff ) && value > best )
{
best = value;
bestx = tx;
besty = ty;
bestdx = -1;
bestdy = 0;
} // Left
tx = x + 0;
ty = y + +1;
value = pathmap.getPixel( tx, ty );
if ( ( ( value ) < 0xffffff ) && value > best )
{
best = value;
bestx = tx;
besty = ty;
bestdx = 0;
bestdy = +1;
} // Down
//Search(+1,-1)
//Search(-1,-1)
//Search(-1,+1)
//Search(+1,+1)
if ( dirxLast == bestdx && diryLast == bestdy )
{ // If we carried on in the same direction, reuse the last point
result[result.length - 1].x = bestx;
result[result.length - 1].y = besty;
}
else
{ // Changed direction, need a new point
result.push({x: bestx, y:besty} );
dirxLast = bestdx;
diryLast = bestdy;
}
// Next point
x = bestx;
y = besty;
}
return result;
}
}
}
Main.as



package
{
import flash.utils.ByteArray;
import flash.utils.getTimer; // Define things common preprocessor directives want.

import flash.display.Sprite;
import flash.display.StageQuality;
import flash.display.StageScaleMode;
import flash.display.Bitmap;
import flash.text.TextField;
import flash.text.TextFormat;
import flash.display.BitmapData;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.display.Graphics;
import flash.geom.Rectangle;
import mylib.Dijkstra;

[SWF( frameRate = "10", backgroundColor = "0x00ffff", width = "640", height = "480" )] public class Main extends Sprite
{
protected var drawing:Sprite = new Sprite;
protected var doing:TextField = new TextField;
protected var router:Dijkstra;
protected var bitmap:Bitmap;
protected var template:BitmapData;
protected var fillTarget:BitmapData;
function Main()
{
// Other stage settings
stage.quality = StageQuality.LOW;
stage.scaleMode = StageScaleMode.EXACT_FIT;
stage.showDefaultContextMenu = true;

// Initialize Router and its display
template = new BitmapData( 640 / 8, 480 / 8 );
FillTemplateWithCrap();
router = new Dijkstra( template );
fillTarget = router.CloneTemplate();
bitmap = new Bitmap( fillTarget );
bitmap.scaleX = 8;
bitmap.scaleY = 8;
addChild( bitmap );

// Initialize graphics child to draw on
drawing = new Sprite;
addChild( drawing );

// Initialize status text
var format:TextFormat = new TextFormat();
format.color = 0xff6666;
format.size = 10;
format.bold = true;
format.font = 'Verdana';
doing = new TextField;
doing.textColor = 0xcecece;
doing.autoSize = "left";
doing.defaultTextFormat = format;
addChild( doing );

stage.addEventListener( Event.ENTER_FRAME, onEnterFrame );
stage.addEventListener( MouseEvent.MOUSE_DOWN, onMouseDown );
}

// Declare persistent state machine data
protected var routeTest:int = 0;
public var routeTest_loop:int = 0;

// State machine mouse click event
protected var bClicked:Boolean = false;
protected var xMouse:int = 0;
protected var yMouse:int = 0;

protected var xStart:Number = 0;
protected var yStart:Number = 0;
protected var xEnd:Number = 0;
protected var yEnd:Number = 0;

// Put the switch in its function
protected function TestRouterInteractive():void
{
// In-function switched FSM
switch ( routeTest )
{
case 0:
{
drawing.graphics.clear();
router.CopyTemplate( fillTarget );
doing.text = "Waiting for starting point.";
}
{
}
routeTest = ( -99 );
return;
case ( -99 ):
{
if ( !( bClicked ) )
return;
}
{
bClicked = false;
xStart = xMouse;
yStart = yMouse;
drawLittleX( drawing.graphics, xStart, yStart, 0xf00000 );
doing.text = "Waiting for ending point.";
}
{
}
routeTest = ( -107 );
return;
case ( -107 ):
{
if ( !( bClicked ) )
return;
}
{ // Wait for first point
bClicked = false;
xEnd = xMouse;
yEnd = yMouse;
drawLittleX( drawing.graphics, xEnd, yEnd, 0xf00000 );
doing.text = "Plotting course...";
}
{
}
routeTest = ( -115 );
return;
case ( -115 ):
{ // Draw fill
;
router.Fill( fillTarget, xEnd / 8, yEnd / 8, xStart / 8, yStart / 8 );
;
}
{
}
routeTest = ( -121 );
return;
case ( -121 ):
{ // Draw initial route
var path:Array = router.Path( fillTarget, xEnd / 8, yEnd / 8, xStart / 8, yStart / 8 );
if ( path.length )
{
with( drawing.graphics )
{
lineStyle( 2, 0x00ffff, 100, true, "none", "none", "none", 1 );
moveTo( xStart, yStart );
for each
( var leg:Object in path )
{
lineTo( leg.x * 8 + ( 8 / 2 ), ( leg.y * 8 ) + ( 8 / 2 ) );
}
lineTo( xEnd, yEnd );
}
for each
( leg in path )
{
drawLittleBox( drawing.graphics, leg.x * 8, leg.y * 8, 0xff0000 );
}
}
}
{
}
routeTest = ( -142 );
return;
case ( -142 ):
{ // Prompt...
doing.text = "Click to continue...";
}
{
}
routeTest = ( -147 );
return;
case ( -147 ):
{
if ( !( bClicked ) )
return;
}
{ // Wait for reset point
bClicked = false;
{
routeTest = routeTest_loop = 0;
}
}
{
}
routeTest = ( 0x7fffffff );
case ( 0x7fffffff ):
break;
default:
{;
routeTest = ( 0x7fffffff );
}
return;
}
{
{
routeTest = routeTest_loop = 0;
}
}
}

// Animation event
protected function onEnterFrame( event:Event ):void
{
// Cycle the switched state machine
TestRouterInteractive();
}

// Mouse button event
protected function onMouseDown( event:Event ):void
{
// Let the state machine know the mouse was clicked.
xMouse = mouseX;
yMouse = mouseY;
bClicked = true;
}

// Draw a little colored X
protected function drawLittleX( g:Graphics, x:Number, y:Number, rgb:int ):void
{
g.lineStyle( 2, rgb, 100, true, "none", "none", "none", 1 );
g.moveTo( x - 2, y - 2 );
g.lineTo( x + 2, y + 2 );
g.moveTo( x + 2, y - 2 );
g.lineTo( x - 2, y + 2 );
}

// Draw a little cell-sized colored box
protected function drawLittleBox( g:Graphics, x:int, y:int, rgb:int ):void
{
g.lineStyle( 2, rgb, 100, true, "none", "none", "none", 1 );
g.moveTo( x, y );
g.lineTo( x + 8, y );
g.lineTo( x + 8, y + 8 );
g.lineTo( x, y + 8 );
g.lineTo( x, y );
}

protected function FillTemplateWithCrap():void
{
const ratio:Number = 0.3;
template.lock();
var x:int;
var y:int = template.height;
while ( y-- )
{
x = template.width;
while ( x-- )
{
if ( Math.random() <= ratio )
{
template.setPixel( x, y, 0 );
}
else
{
template.setPixel( x, y, 0xffffff );
}
}
}
template.unlock();
}

}
}
Oh, and as far as a mini-map goes... you'll have all of your characters in some sort of common map coordinate space. Just scale that down and assign colored dots to their positions instead of MovieClips.

added...
Also more about building that stuff here...
http://flex2cpp.sourceforge.net/
https://sourceforge.net/projects/flex2cpp

[Xxspade13xX]

Thanks a lot. I'll try out the code.

[pingnak]

No problems. You might want to go to the sf site, though as I improved it markedly over the quick little hack I posted.