Printable View
no these are good questions, i'm wondering the answer to that last one to cause i want to implement this zone technique.
iopred :D
EDIT - that multiple exits and entrys just put me off a little, too confusing to update i think especially when terrain changed. I guess i'm going with my chunk idea, so that there's a chunk between every node, which would avoid that situation but might be slower.
:(
whats a girl to do
Hmm ok, I think I get it, thanks. I dont know how I would go about coding something like that though where the entry and exit points of zones could change at any time.. how you would know when to add/remove entry/exit points seems a bit complex to me. Still, better leave that to the people who know what they are doing ;).
Ali
[EDIT]
ok, looks like i'm not the only one put off by that ;)
Alternatively, if you want to make it simpler, you could say that every tile has N number of entry points. Where the default ones would be: Each border, each corner. So by default theres 8, or you could say theres 12 with 2 along each border (but then you're increasing the complexity of the large search a bit too much)
ok, step 1 out of 5000
node based pathfinding
http://img103.imageshack.us/my.php?i....swf&width=800
its using Dijkstra's algorithm, i quickly discovered that A* wasn't going to cut it, as paths with less nodes might not be the best.
however, i think it may be operating closely to A* because i state that when the goal node is found, stop searching for any more paths, simply taking this out usually returns the same result and is faster. But i'll do more tests to see if i really need that path accuracy.
so on my first attempt at nodes this is how i've approached it:
go through map, find edges, add to node array
go through node array, check other nodes, cast a ray to determine connections
adding start point - go through all nodes, cast a ray, add connections to start node
adding goal point - go through all nodes, reset connection list, cast a ray, add connections to nodes
run pathfinding
-NOTE- start point doesn't cast a ray to end point, so nodes will be considered when a path from start to goal is available (i'm lazy)
------
- now all is well and it works how i would like, most searches are around 1 - 2ms. Now about zoning, if i use the chunk idea which means there are only chunks between moveable sections of terrain i don't have to cast rays to find connecitons, simply go through the current chunk and adjacent chunks and link up nodes, no exit and entry points needed (i think)
- or i use Zones, which i still think needs raycasting, but there will be much much much less zones to consider when find the (zone / chunk level) path before deepening to node level. Also this would require entry and exit points which were discussed earlier
- also i would like to merge some nodes into one (not sure how to go about that either)
i haven't got a clue how i'm going to define these chunks or zones yet. So i was wondering if anyone has a source or could point me to a nice juicy link
I really feel that there has to be different depths of pathing to eliminate certain nodes.
Anyway, just thought id show some progress :) and thanks for any help
Link doesn't work for me, but that may just be me. :p
http://soap.com.au/rts
silly imageshack
A* will return the shortest path, as long as your Heuristic is correct, and with less nodes touched.Quote:
Originally Posted by mr_malee
yeah i thought that too, maybe i messed something up when i changed over to nodes. Hmmm, i'll try this out again then
ok well i'm not sure what i'm using now, i think its A* because every node isn't checked and the search stops when the goal becomes the parent node.
F value = parentCost + costToParent + costToGoal
this greatly reduces the search, i was doing:
F value = parentCost + costToParent
so here's the results, i guess looking into different heuristics is a must.
a* - http://img520.imageshack.us/my.php?i....swf&width=800
node with good H - http://img520.imageshack.us/my.php?i....swf&width=800
node with bad H - http://img168.imageshack.us/my.php?i....swf&width=800
thanks iopred for making me re-investigate :)
NOTE - drawing those lines affects peformance slightly
It looks like nodes are reintroducing themselves to the search.. What I mean is.
You have nodes A B C D,
The search goes: A, B, C and then when checking nodes connected to C it readds A!
You can solve this by using an iterator, so if the iterator in the node doesn't match the current search iterator, add it and set the iterator in the node. Otherwise you ignore it because it's already being acted upon.
You can do this without worrying about incorrect searches, unless the time to get to that node is negative (unlikely) because otherwise you are guaranteed a longer search through that node.
Ignore me if this isn't the case :)
Also, is the good heuristic Manhattan? I've found it's fast to calculate and the best in almost all circumstances, also guaranteed to be fastest route (Math.abs(x1 - x2) + Math.abs(y1 - y2))
yeah whoops, that was me putting the line draw before the check
EDIT - using the goal distance shortens the checks but sometimes will choose inaccurate paths :(
Ah nice, I edited my above post, asking about your heuristic.
Hi,
I implemented an A* pathfinder with nodes in AS1 two weeks ago. Did not test it much, but I got always the shortest path in my exmaples.
Maybe you can find soemthing useful in my code:
The node class:
The priority queue class:Code:function Node(x, y) {
this.next;
this.parent;
this.costFromStart = 0;
this.estimatedCostToGoal = 0;
this.neighbour = [];
this.x = x;
this.y = y;
}
Node.prototype.getCost = function() {
return this.costFromStart+this.estimatedCostToGoal;
};
Node.prototype.getEstimatedCost = function(node) {
var dx = this.x-node.x;
var dy = this.y-node.y;
return dx*dx+dy*dy;
};
..and the A* implementationCode:function PriorityQueue() {
this.head;
this.size = 0;
}
PriorityQueue.prototype.enQueue = function(node) {
var temp = this.head;
var prev;
while (temp != undefined && temp.getCost()<=node.getCost()) {
prev = temp;
temp = temp.next;
}
if (prev == undefined) {
this.head = node;
} else {
prev.next = node;
}
node.next = temp;
this.size++;
};
PriorityQueue.prototype.deQueue = function() {
var temp = this.head;
this.head = this.head.next;
this.size--;
return temp;
};
PriorityQueue.prototype.contains = function(node) {
for (var i = this.head; i != undefined; i=i.next) {
if (i == node) {
return true;
}
}
return false;
};
I wrote some function in order to search and remove elements in the closed array:Code:function findPath(startNode, goalNode) {
open = new PriorityQueue();
closed = [];
startNode.estimatedCostToGoal = startNode.getEstimatedCost(goalNode);
open.enQueue(startNode);
while (open.size) {
var node = open.deQueue();
if (node == goalNode) {
//trace your path
return;
}
for (var i in node.neighbour) {
var neighbourNode = node.neighbour[i];
var isOpen = open.contains(neighbourNode);
var isClosed = contains(neighbourNode, closed);
var costFromStart = node.costFromStart+node.getEstimatedCost(neighbourNode);
if ((!isOpen && !isClosed) || costFromStart<neighbourNode.costFromStart) {
neighbourNode.parent = node;
neighbourNode.costFromStart = costFromStart;
neighbourNode.estimatedCostToGoal = estimatedCostToGoal.getEstimatedCost(goalNode);
if (isClosed) {
remove(neighbourNode, closed);
}
if (!isOpen) {
open.enQueue(neighbourNode);
}
}
}
closed.unshift(node);
}
}
Code:function remove(obj, list) {
for (i in list) {
if (list[i] == obj) {
list.splice(i, 1);
}
}
}
function contains(obj, list) {
for (i in list) {
if (list[i] == obj) {
return true;
}
}
return false;
}
Looking good malee :). Just curious, have you tried adding things to the map at runtime yet? You would have to recalculate the node connections each time the environment chanegd right? Would that be much of a performance hit?
Ali
nope not yet. I think zoning has to be in place before i tackle that, don't want to cast aray to every single node in the game. Only to nodes in the zone.
But basically i think i would just add a connection to the existing node and the new node. Also terrain costs like mud can be added into the cost of the connection when casting the ray. The ray just adds up the cost of tiles it accessed and then i give that to both connections.
well i think so anyway, expect something tommorrow :D
andreaskrenmair - thanks but i thinik i've got it figured now :)
yet i dont see a advantage to grid based pathfinding as youŽll propably struggle with the crurrent attempt when it comes to interactive elemnts,- things that can alter each frame.
Because if youŽd uspport interactive elemnts youŽd have to recalculate the node endings on the grid and depneding on how changes were made this could cost CPU time.
As for the node points,- did you automaticly generate them or placed them manually? Maybe you remember but I did the same some time ago with my orthographic engine- just noticed that the automatic mode to CPU intense and somtimes to accurate (on vectors).
But with your grid as base and AS3 it could be alot faster and accurate enough,- maybe only recalculate a certain zone on where elments changed.
We were just talking about that render ^^
Ali
i think its going to have to mix tilebased with node based, maybe solid terrain like the cliff's, walls building's can be node based (things that don't move) things that do move like units will need their own collision avoidance, maybe normal tilebased approach. A unit is givin a path to move on, whenever it enters a new cell, check the next cell for any other objects, then run a path around that object, use that new path, when we reach the end continie on the node path. Of course paths will be bigger than they need to be because the nodes don't take into account other units. I could also treat a mass of units as a rectangle and plot 4 nodes at each edge.Quote:
Originally Posted by renderhjs
as for the generation of nodes, its automatic, when the map is being built it checks if a tile is solid and finds its edges, if its an edge it becomes a node, not very CPU intesive at all. I'm looking to merge these nodes somehow
hopefully i'm not annoying people with my posts in this thread.
anyway, little update
http://soap.com.au/rts
its got some graphics, yah, not mine of course but it helps me to build the system better, terrain costs are in, which is the current problem :(
now it al works as it should (hopefully) and the best path should be chosen. However there now must be more nodes indicating corners of changing terrain and costs between different connections, thus meaning i'm getting closer and closer to A* while still better the complexity of nodes is starting to show a little
to lessen the search time i've thought of these:
don't use path costs, make the user choose good small paths :)
don't let raycast make connections to far away nodes (this might be good or bad, not sure)
use a hash table to look up path costs. Currently when a map is loaded, its builds a weight map based on a white & black bitmapData which mimicks a tileset, white is solid, and bacl contains different alpha values for cost, full black would be 1 (most) 0 (least), so when the maps being built, rays are cast from nodes to connected nodes and a cost is returned, the node then formats this cost into an associative array (which i don't want) like so: node[6][x+" "+y] = raycast.cost. Search times can increase up to 20ms which i don't like at all. I think array access will just be the same. So i need some way of accessing path costs between nodes really efficently. Any ideas?
thanks for putting up with this :)
EDIT - rolling the mouse outside of the window causes an error. Probably because its trying to access a tile that dont' exist
ah sorry bout that ali, must have been way to excitedQuote:
Originally Posted by alillm
not at all :)Quote:
Originally Posted by mr_malee
runs noticeable slower (much slower) :(
as for the search,- how about reducing nodes that have the same vectors and follow after each other? because if I walk just down it generates many sub- nodes that arenŽt necessary- atleast thatŽs what I did with my engine and it helped alot.