Non-tile based pathfinding?

[zuperxtreme]

Hey guys,

I'm looking for a way to pathfind without using tiles. I'd like diagonal movement in my game and, as far as I know, tile based doesn't really let you(I'm probably wrong, if so let me know).

I basically need the player to go to a location where the mouse was clicked, but there are walls and obstacles as he will be inside a building.

Any ideas?

I was starting to read about "Graph ADT" in kirupa, so maybe that'll be the answer.

Anyways, thanks.

[lautan]

You can move diagonally in a tile-based game. You just need to make a small change. Its best to go with a tile-based game approach.

[LCurtis]

You could work out some kind of path system using nodes to guide the AI. When a place is clicked you loop through an array of nodes and find the nearest one. Then you find which node is close to the entity that you are moving. Then you simply interpolate the entity through the path of nodes. Its kind of complex and going to take some research before you can sit down and code it.

[CaptinChu]

First, use base tiles to find the most efficient route to that particular point. Those base tiles are just for a reference, NOT to be used as a guide for actual movement.

For diagonal movement, adjust the x and y to have a slope that will go through two points, since the quickest route between two points is a straight line. (I assume you're using Euclidean Physics.) YOU MUST HAVE A FIXED SPEED! (Let this speed be defined as the variable "s")

The next part is to find out the difference in x and the difference in y between the two points. That's easy:

x=(x1-x2)
y=(y1-y2)

Where m is slope.

The tricky part is moving the player at a constant speed. That requires the Pythagorean Theorem.

r=sqrt(x^2+y^2)/s

What I'm doing is comparing the entire line length of the diagonal (the length of the hypotenuse is defined as sqrt(x^2+y^2) ) to the speed. That will get a speed ratio that will work for both x and y. The speed the character will go at will be:

s=10 // some constant speed

dx=(x1-x2)
dy=(y1-y2)

r=sqrt(x^2+y^2)/s

Character._x+=dx/r
Character._y+=dy/r

The moment that the character hits that point, (Shapeformed hittest with character against point), it will go to the next point in the same fashion. Good luck.

[zuperxtreme]

Also, a bit of help with the moving and collition detection? :(

http://www.freewebs.com/zuperxtreme/FLAS H%20TESTS/Single%20player%20overview.htm l

var moveMouseListener:Object = new Object();
speed = 1;
moving = false;
hit = false;
function onEnterFrame() {
	moveLeader(leader);
	//trace("Leader coords: X-"+leader._x+" | Y-"+leader._y);
	//trace("waypoint coords: X-"+waypoint._x+" | Y-"+waypoint._y);
}
function moveLeader(MC) {
	moveMouseListener.onMouseUp = function() {
		_root.attachMovie("waypoint", "waypoint", 200, {_x:_xmouse, _y:_ymouse});
	};
	moveUnit(leader, waypoint);
	if (checkForCollision(MC, room)) {
		hit = true;
	} else {
		hit = false;
	}
}
Mouse.addListener(moveMouseListener);
function moveUnit(MC, waypoint) {
	Radians = Math.atan2(waypoint._y-MC._y, waypoint._x-MC._x);
	Degrees = Math.round((Radians*180/Math.PI));
	yChange = Math.round(waypoint._y-MC._y);
	xChange = Math.round(waypoint._x-MC._x);
	yMove = Math.round(yChange/20);
	xMove = Math.round(xChange/20);
	trace("Y: "+yMove+" X:"+xMove);
	if (_root.hit) {
		MC._y -= yMove;
		MC._x -= xMove;
	} else {
		MC._y += yMove;
		MC._x += xMove;
		//MC._rotation = Degrees-90;
	}
}

And this is the gskinner collision class I modified and used(if there are better ways, let me know, please):

import flash.display.BitmapData;
import flash.geom.ColorTransform;
import flash.geom.Matrix;
import flash.geom.Rectangle;

function checkForCollision(p_clip1:MovieClip,p_clip2:MovieClip,p_alphaTolerance:Number):Rectangle {
		
		// set up default params:
		if (p_alphaTolerance == undefined) { p_alphaTolerance = 255; }
		
		// get bounds:
		var bounds1:Object = p_clip1.getBounds(_root);
		var bounds2:Object = p_clip2.getBounds(_root);
		
		// rule out anything that we know can't collide:
		if (((bounds1.xMax < bounds2.xMin) || (bounds2.xMax < bounds1.xMin)) || ((bounds1.yMax < bounds2.yMin) || (bounds2.yMax < bounds1.yMin)) ) {
			return null;
		}
		
		// determine test area boundaries:
		var bounds:Object = {};
		bounds.xMin = Math.max(bounds1.xMin,bounds2.xMin);
		bounds.xMax = Math.min(bounds1.xMax,bounds2.xMax);
		bounds.yMin = Math.max(bounds1.yMin,bounds2.yMin);
		bounds.yMax = Math.min(bounds1.yMax,bounds2.yMax);
		
		// set up the image to use:
		var img:BitmapData = new BitmapData(bounds.xMax-bounds.xMin,bounds.yMax-bounds.yMin,false);
		
		// draw in the first image:
		var mat:Matrix = p_clip1.transform.concatenatedMatrix;
		mat.tx -= bounds.xMin;
		mat.ty -= bounds.yMin;
		img.draw(p_clip1,mat, new ColorTransform(1,1,1,1,255,-255,-255,p_alphaTolerance));
		
		// overlay the second image:
		mat = p_clip2.transform.concatenatedMatrix;
		mat.tx -= bounds.xMin;
		mat.ty -= bounds.yMin;
		img.draw(p_clip2,mat, new ColorTransform(1,1,1,1,255,255,255,p_alphaTolerance),"difference");
		
		// find the intersection:
		var intersection:Rectangle = img.getColorBoundsRect(0xFFFFFFFF,0xFF00FFFF);
		
		// if there is no intersection, return null:
		if (intersection.width == 0) { return null; }
		
		// adjust the intersection to account for the bounds:
		intersection.x += bounds.xMin;
		intersection.y += bounds.yMin;
		
		return intersection;
	}

[zuperxtreme]

Thanks for the replies guys. I'm trying to figure out the movement now..