#97632 - batblaster - Thu Aug 10, 2006 10:01 pm
Hi,
someone have a A*pathfind routine who work on GBA without using to much ram ? I have an example who work on VC but use a lot of ram and i can't use on GBA with 256k..
Thanks in advance.
_________________
Batblaster / 7 Raven Studios Co. Ltd
------------------------------------------
#97764 - sgeos - Fri Aug 11, 2006 1:23 pm
A* is expensive. How big are your maps? You might want to consider "something else" if you have large maps. My books are far far away, so I can't name "something else" right now.
-Brendan
#97780 - Spaceface - Fri Aug 11, 2006 2:53 pm
Yeah A* is very expensive. However pathtracing like pacman was done with much less RAM. Maybe you should considder finding a less expensive algoritm.
#97799 - sajiimori - Fri Aug 11, 2006 4:49 pm
The cost really depends on the size of your data. It's not prohibitively expensive if you use a sparse graph, as opposed to having a node for every tile on the map.
In fact, that's the only way I've ever used A*...
#97876 - keldon - Sat Aug 12, 2006 2:37 am
Have you thought of iterative deepening? It is ideal for little amounts of ram, and is also computationally efficient.
#97893 - batblaster - Sat Aug 12, 2006 5:17 am
Sorry for my delay , i was out...
My maps are 128x128 tiles and also the collision level is 128x128...
I must follow with an enemy a target...
The enemy is on map but didn't move, if it see you , because you go inside his visual range, he start walking following you... if touch you , you lose.
If someone can suggest what is better i'm happy to try...
I see the A* because i found a tutorial and an example who do exactly what i need but after , looking at the source, i see it use many many arrays...
I'm free for any solutions...
Thanks..
_________________
Batblaster / 7 Raven Studios Co. Ltd
------------------------------------------
#97920 - keldon - Sat Aug 12, 2006 10:15 am
#97994 - sajiimori - Sat Aug 12, 2006 6:45 pm
One thing to note is that there's a huge difference in efficiency between "educational" A* implementations (or simply amateurish ones) and ones that are optimized for time and space. I'm talking an order of magnitude, at least. The amount of waste in most implementations is just apalling.
If your graphs are statically determined, they can be in ROM. As for workspace, you can get away with just 2 or 3 words per node, if you pack the data right.
In general, you only need enough nodes so that the AI will always have a clear line of sight to at least one node. In practice, that's usually not very many!
#97999 - tepples - Sat Aug 12, 2006 7:02 pm
| sajiimori wrote: |
| In general, you only need enough nodes so that the AI will always have a clear line of sight to at least one node. In practice, that's usually not very many! |
For example, a Pac-Man clone would need nodes only at intersections, right?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#98008 - sajiimori - Sat Aug 12, 2006 7:21 pm
Right. Even more generally speaking, it's not so much about line-of-sight as it is about the availability of a non-graph-based algorithm that allows the AI to reach a graph node. For instance, if your lower-level seek algorithm allows characters to find their way around small obstacles (like furniture), then you don't need nodes on all sides of such objects.
#98021 - keldon - Sat Aug 12, 2006 8:17 pm
| sajiimori wrote: |
| Right. Even more generally speaking, it's not so much about line-of-sight as it is about the availability of a non-graph-based algorithm that allows the AI to reach a graph node. For instance, if your lower-level seek algorithm allows characters to find their way around small obstacles (like furniture), then you don't need nodes on all sides of such objects. |
Good point.
#98029 - sajiimori - Sat Aug 12, 2006 8:55 pm
As an aside, I gotta endorse the oft-neglected idea of a "seek" test (which may have an official name, but that's what I've been calling it). The test asks: If I were at point A, could I get to point B without using the graph, and if so, how?
Such a test is crucial for natural-looking navigation when using a sparse graph. Without it, characters are bound to do stupid things like walk all the way to the nearest node and back just to reach a point that was right next to them. Also, their movement looks mechanical, as if they're on a rail, whereas real people will cut corners when possible.
You can get natural-looking navigation by continuously trying to seek to the destination after your current one. Then the AI will cut corners as soon as the way is clear.
In my last two games, seek tests were fairly expensive, so they were done in an iterative manner that split up the work across multiple frames. The lag caused by the iterative approach had the amusing side-effect that the characters would start going to a node, then a couple frames later realize that they can go straight to the node after. When that happened several times in a row (which was rare), they'd dance around for a second as they tried to pick a direction. :)
#99099 - nrx - Sat Aug 19, 2006 3:28 pm
In case someone is interested, I implemented a pathfinder in my tech demo "GOD".
As explained in the readme file: | Quote: |
| This tech demo allows the player to move around the map, and dynamically add and remove walls. The pathfinder is activated and finds the shortest path from the building in the center of the map to any of the 4 targets in the corners (the path is computed and displayed every time the map is modified). |
You'll see that although it's an implementation of the A* algorithm, it doesn't use too much CPU nor RAM (which was important to me as the graphic engine also needs some CPU ;-)).
Source code and ROM are available for download here.
#99155 - sajiimori - Sat Aug 19, 2006 8:59 pm
Looks like a 64x64 map uses around 22 KB, and a 128x128 map uses around 84 KB.
#103426 - Miked0801 - Thu Sep 21, 2006 10:12 pm
I got a full-fledged A* like search to work on GBC with 64x64 maps with 10K of memory (4K paged) (Heroes of M&M). With creativity, you can get it to fit...
#103446 - keldon - Fri Sep 22, 2006 12:33 am
| Miked0801 wrote: |
| I got a full-fledged A* like search to work on GBC with 64x64 maps with 10K of memory (4K paged) (Heroes of M&M). With creativity, you can get it to fit... |
But if all of the edges are of equal length (assuming they are in a map based search), then what does A* have over iterative deepening?
#103460 - tepples - Fri Sep 22, 2006 3:40 am
In a map based search, you can precompute corners of the walls and set those as A* nodes, skipping all the map cells between corners.
Efficient iterative deepening needs some heuristic to discard paths that are going the wrong way. With the most obvious heuristic (sort paths by distance traveled plus estimated distance left to go), it becomes A*.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#103469 - sajiimori - Fri Sep 22, 2006 4:18 am
As far as I know, the A* algorithm itself doesn't define what kind of heuristic is used -- it just specifies that some heuristic is used.
To illustrate how A* can be better than iterative deepening, imagine a character that's trying to find a path to a tile 4 spaces to his right. The way is clear, but he doesn't know it yet.
With iterative deepening, he'll check above, below, to the left, and to the right, all on the first iteration.
With A* (using distance as a heuristic), he'll go straight to the right and hit the destination without checking any other tiles. He'll only check other ways if the most direct route is blocked.
Additionally, iterative deepening repeats the early parts of the search over and over, until it reaches a depth at which the destination can be reached.
In fact, it can be proven that there is no better general pathfinding algorithm than A*.
#103473 - tepples - Fri Sep 22, 2006 4:45 am
But game pathing is not general: - Maps are generally planar, and the obvious heuristics may not take advantage of this.
- Maps are often grids, and the obvious heuristics may not take advantage of this.
- Can A* finish within 280,000 CPU cycles (important on a 16.78 MHz machine)?
- Can A* give a path and revise it as the graph changes?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#103481 - sajiimori - Fri Sep 22, 2006 6:11 am
Design heuristics as appropriate. You may find that the simplest thing is good enough. Even a very simple heuristic is way better than none at all.
Hell yeah, A* can finish in 280,000 CPU cycles! It obviously depends on the situation, but for typical cases, I'd expect A* to greatly outperform unguided searches of every kind, and the benefit will only increase with graph complexity.
Whether you choose to revise your path over time doesn't seem dependent on which low-level pathfinding algorithm you choose. Typically, you'll want to assemble a complete path, and then recalculate perodically if desired, or on an event-driven basis. For example, a breaking window might broadcast a message that notifies pathfinders that a new edge is available that passes through the window pane.
I personally haven't had need of such techniques yet. The environments in my games have been pretty static so far. It seems pretty simple to implement, though.
Edit: I wanted to bring up a technique used by a coworker of mine. It's especially good for systems with a lot of random-access ROM, and very limited RAM and CPU. It doesn't scale to large graphs, so sparse graphs may be important.
The technique is: For each node, find an optimal path to every other node, drop everything but the first step, and write that step to the ROM. It's O(1) pathfinding with zero RAM usage.
If you limit number of neighbors to 4, you can fit a 256 node graph in 16 KB of ROM, or a 512 node graph in 64 KB.
Last edited by sajiimori on Fri Sep 22, 2006 8:46 am; edited 1 time in total
#103487 - sgeos - Fri Sep 22, 2006 7:43 am
| sajiimori wrote: |
| Hell yeah, A* can finish in 280,000 CPU cycles! It obvious depends on the situation, but for typical cases, I'd expect A* to greatly outperform unguided searches of every kind, and the benefit will only increase with graph complexity. |
I think the real answer is "it depends, but generally yes."
| sajiimori wrote: |
| Edit: I wanted to bring up a technique used by a coworker of mine. It's especially good for systems with a lot of random-access ROM, and very limited RAM and CPU. It doesn't scale to large graphs, so sparse graphs may be important. |
You could use sectors or a bunch of other approaches to counter the x^2 properties of larger maps. You could either match the boarders of your sectors, or treat the edges of you map as sector transition zones. What you'll end up with is a huge table of local transitions, and a smaller (maybe) table of sector tranisitions. If your destination is in another sector, you head to that sector. If not, you head to the destination.
Would keeping the sector and local table sizes close to the same size be the best way of saving space? What about a fractal approach? Macrosectors, sectors, subsectors, nodes? Each with transition tables. Seems like you might be able to get stuck, depending on the maps. How often do you want to make something so big?
| sajiimori wrote: |
| The technique is: For each node, find an optimal path to every other node, drop everything but the first step, and write that step to the ROM. It's O(1) pathfinding with zero RAM usage. |
With compression or smart data pack you might be able to get away with less.
| sajiimori wrote: |
| If you limit number of neighbors to 4, you can fit a 256 node graph in 16 KB of ROM, or a 512 node graph in 64 KB. |
In theory you might be able to run your search through a RAM patch table to handle dynamic maps. It would depend on how much changes by breaking your window.
-Brendan
#103510 - madmax - Fri Sep 22, 2006 3:18 pm
Hey there I agree that you shouldn't try and use A* on the GBA. Mainly cause I have an A* algorithem on a java game that runs on PC and it's a big performance hit even on a PC (the fact I used java won't help). A* is not to smart because you always have to solve the whole path before you can know which way to go. And in a game where your characters follow other characters the paths will change constiantly and have to be recalculated a lot.
In my GBA project I use area nodes and precalculated paths. Basically what area nodes are, nodes with positions and sizes you can think of them as filling an area of the map, unlike A* my nodes are interlinked but only at design time and the links can be throwen away later. I have all parts of the map that are supposed to be accessible to my entitys partitioned by these area nodes. I then I feed all my nodes with their links on which nodes are valid transitions into a pathfinding program which precalculates all the best paths between the nodes and gives me a source code for a array containing all nodes and a index array containing all the paths
At runtime when you need a path you put your can lookup the proper path quickly from the paths array and follow it. You will never need to calculate a path that will be throwen away.
The only drawback of this is that it only works for static obsticals you need some smart ai to prevent collisions between dynamic obsticals.
Theres an intresting artical on this at http://www.gamedev.net in their resources section. I haven't supplied a full path because you need to be a member to access it but good news is membership is free.
_________________
John Noon
#103532 - keldon - Fri Sep 22, 2006 5:54 pm
| sajiimori wrote: |
As far as I know, the A* algorithm itself doesn't define what kind of heuristic is used -- it just specifies that some heuristic is used.
To illustrate how A* can be better than iterative deepening, imagine a character that's trying to find a path to a tile 4 spaces to his right. The way is clear, but he doesn't know it yet.
With iterative deepening, he'll check above, below, to the left, and to the right, all on the first iteration.
With A* (using distance as a heuristic), he'll go straight to the right and hit the destination without checking any other tiles. He'll only check other ways if the most direct route is blocked.
Additionally, iterative deepening repeats the early parts of the search over and over, until it reaches a depth at which the destination can be reached.
In fact, it can be proven that there is no better general pathfinding algorithm than A*. |
Isn't it the other way around?
Besides, if you have different length edges then although you have found your destination you still do not know that you have the shortest path. Also in A* he will have to check every edge first to start with the shortest edge.
But in the scenario where all of your lengths are equal then iterative deepening will stop when you reach the destination anyway. ID is meant to be the faster of the algorithms for searching. The reason why is because with each iteration of A* you will have to check every child node from your open list. This is what happens with a 5x5 space starting from the centre searching for the worst case of it being in the last node that it looks at:
- iteration 1: search space = 4 nodes
- iteration 2: search space = 6 nodes
- iteration 3: search space = 7 nodes
- continued in short: 8,8,9,10,11,12,11,11,10,9,8,8,7,7,6,5,4,3,2,1
With ID it's 4,16,33,50
** although this needs to be verified by an algorithm; I'm halfway in between installing eclipse so I can do it later, i might be way off.
As for that technique of a precalculated map, that is a good optimisation but how do changing maps affect this? I have ideas in my head, but I'm sure you've covered this and have a full answer already.
| Quote: |
| Edit: I wanted to bring up a technique used by a coworker of mine. It's especially good for systems with a lot of random-access ROM, and very limited RAM and CPU. It doesn't scale to large graphs, so sparse graphs may be important. |
But increasing the branching factor will increase the search space a lot as you will still have to store the minimum distance to complete the graph. Although you can store just the edges of length one from the destination node.
#103550 - sajiimori - Fri Sep 22, 2006 7:52 pm
madmax,
Read the thread. You'll note that more than one of us has shipped handheld games that use A*. Also note my comment that naive A* implementations... well, they suck. I wouldn't be surprised if such an implementation caused you trouble.
Regardless of which algorithm you use, if you don't solve the whole path, your first step could be a bad one, even in a static environment. If you're willing to accept that, then you're outside the domain of pathfinding algorithms, and in the domain of "let's just go straight there and hope nothing's in the way."
Following your trend of ignoring the thread contents, you apparently didn't notice that I already described the "precalculated path" system.
keldon,
A* is guaranteed to find the shortest path, but you provide the definition of what "shortest" means. If you decide that "shortest" means "least number of nodes along the path," then you might be dissatisfied with the answer. (Such a measurement gives equal cost to all edges.) It's typical to measure based on distance, perhaps also considering the difficulty of traversing the terrain.
| Quote: |
| Also in A* he will have to check every edge first to start with the shortest edge. |
Yes, you expand the first node, but in the example I gave, you wouldn't expand any unnecessary nodes. (I should have been more clear about that.) Slight correction: you don't look for the shortest edge; you look for the one with lowest estimated whole-path cost, which could very well be the longest of all the edges.
Both iterative deepening and A* will stop when they reach the destination.
| Quote: |
| The reason why is because with each iteration of A* you will have to check every child node from your open list. |
False. You should have a queue of nodes, with the cheapest at the front. Finding the next node to visit doesn't involve a search -- it involves popping the first node off the queue.
sgeos suggested a technique for handling map changes for precompiled paths.
| Quote: |
| But increasing the branching factor will increase the search space a lot as you will still have to store the minimum distance to complete the graph. Although you can store just the edges of length one from the destination node. |
Distances are not represented at all using this technique. If you're starting at node A, and you want to get to node B, you look up "index B" in the array of "first steps" in node A. At the second node, you again look up "index B," and that gives you the third node, and so on.
Increasing the possible number of neighbors increases the data size because you need more bits to uniquely identify a neighbor. 2 bits is enough to select between 4 possible neighbors, so you have n^2 * 2 bits.
If you want 8 neighbors, then it's n^2 * 3 bits. The size increases logarithmically with the number of neighbors you want to support.
#103572 - keldon - Fri Sep 22, 2006 9:30 pm
| Quote: |
| A* is guaranteed to find the shortest path, but you provide the definition of what "shortest" means |
I wasn't talking about ID finding a shorter path, just that it is really efficient. But now I think of it, the one I implemented, and probably what you did is much faster; <<mentioned later>>.
| Quote: |
Yes, you expand the first node, but in the example I gave, you wouldn't expand any unnecessary nodes. (I should have been more clear about that.) Slight correction: you don't look for the shortest edge; you look for the one with lowest estimated whole-path cost, which could very well be the longest of all the edges.
Both iterative deepening and A* will stop when they reach the destination. |
I know how A* works ^_^ I meant shortest estimated total cost. And I was talking about ID stopping because it sounded a little like you was implying that ID would continue searching after it found the destination. Must have misunderstood; I was glancing at a couple of pages when reading your post.
| Quote: |
| False. You should have a queue of nodes, with the cheapest at the front. Finding the next node to visit doesn't involve a search -- it involves popping the first node off the queue. |
Oh yeah, same algo I used for finding paths with A*; it's just that we've been working with variable edge lengths in AI. I was thinking of adding them to an ordered list, but I handled that seamlessly in my A* algo.
| Quote: |
| Distances are not represented at all using this technique. If you're starting at node A, and you want to get to node B, you look up "index B" in the array of "first steps" in node A. At the second node, you again look up "index B," and that gives you the third node, and so on. |
Oops, I misread your line. I thought you was moving on to something different where you pre calculate multiple distances, so where you could arrive in 2 steps, etc; don't know where that came from.
#104511 - Yare - Fri Sep 29, 2006 10:59 pm
An alternative to running grid-based A* would be to generate a walkmesh.
Partition your level into convex, walkable polygons.
Link the polygons with common edges in a graph.
Run A* using the walkmesh, OR create a lookup table containing paths from every polygon to every other polygon that is generated along with the level.
You can trade CPU for RAM. You always have to make a sacrifice somewhere though.
Otherwise if your levels are simple enough you could look at steering behaviors, or maybe just have the player's movement generate a path that the chasing object will follow.
*shrug*
#104523 - sajiimori - Sat Sep 30, 2006 2:00 am
Yes, if I had a game with more complex pathfinding requirements than I've done so far, then I'd consider the approach you described, Yare. As it is, rolling hills cause my AI to pause and think for a while because it has to trace over all the slopes to realize that it can walk straight across. If it viewed the whole area as a single polygon, it wouldn't have to think so hard.
In a game with jumping, when there's a floor above another floor, the lower floor sometimes has to be subdivided along the edges of the upper one, so that there's a distinction between "on the bottom floor, directly under the upper one" and "on the bottom floor, with jumping access to the upper one." There should be a graph edge connecting the latter pair, but not the former.
#106691 - Yare - Sun Oct 22, 2006 7:34 pm
| sajiimori wrote: |
| As it is, rolling hills cause my AI to pause and think for a while because it has to trace over all the slopes to realize that it can walk straight across. |
If your pathfinding is mostly in the direction from the start to goal and is relatively open (not maze-like), then you could try weighting your hueristic (distance estimate) slightly greater than 1 (1.2 works pretty well in my experience). This will cause the algorithm to tend towards the goal instead of away from it when pathfinding.
Otherwise, for what you've described a waypoint or corner graph sounds like it would work nicely.
#106826 - sajiimori - Mon Oct 23, 2006 8:36 pm
The behavior of the A* portion of my pathfinding code has been fine; I don't even bother splitting up the search across multiple ticks because it's so fast.
Even still, the AI won't start walking until it has done collision traces to make sure it can reach its (immediate) destination, and that's where rolling hills can be a little stressful. For n changes in slope (uphill or downhill) between the start and destination, it can take (n/2)*3 game loops before the character starts walking, or worse if the first test fails and another attempt is needed.
It's definitely optimized for low-poly environments! :)
#106843 - Yare - Tue Oct 24, 2006 2:21 am
| sajiimori wrote: |
| It's definitely optimized for low-poly environments! :) |
Pardon my ignorance, but why are you having your entities pathfind over the hills? Assuming that the entire hill is walkable you can simply let the physics system adjust their height as they walk across, can you not?
It seems like it would be easier to pathfind straight across the hill using the slope as a movement cost weight.
#106845 - sajiimori - Tue Oct 24, 2006 3:06 am
Of course, the collision system will make them walk along hills, but the idea is to not walk until you know the way is clear.
There are two main reasons that an algorithm is needed to determine whether it's possible to walk directly from one point to another. First, you have to be able to get from any position to some node of the graph in order to make use of it. Second, natural motion (that doesn't look like it's on rails) requires that you skip ahead to later nodes when the way is clear.
#106849 - Yare - Tue Oct 24, 2006 4:50 am
| sajiimori wrote: |
| Of course, the collision system will make them walk along hills, but the idea is to not walk until you know the way is clear. |
What I would do in a search space like this is "flatten" the hills.
So if your hill with an obstruction on top looks like:
| Code: |
____
B | | C
___|__|___
/ \
/ \
/ \
----/ \-----
A D
|
Then the search space you generate for that hill ought to look something like this:
| Code: |
A ------> B XXXXX C ------> D
<------ <------
|
Where B and C do not have an edge connecting them because there is an unpassable obstruction. Alternatively, you could add data to the edge specifying the minimum "jump" height required to successfully navigate from B to C or vice versa, etc... You could also store slope information on the edges to be used for a variety of movement calculations.
#106910 - sajiimori - Tue Oct 24, 2006 6:46 pm
Yes, I have considered several ways to reduce the number of traces that are done. Defining 2D polygonal sectors that are trivially traversable amounts to flattening the hills.
As it is, I haven't needed to generate search spaces at all.