Hey guys. I’m trying to decide what direction to go in regards to a path finding system for an iPhone game. I understand that some systems (like A-star) might be more taxing than others.
My basic goal is to navigate the player character from A-to-B in a point-and-click style. I would like the player character to be able to get from A-to-B while intelligently avoiding obstacles in his path. I don’t mind doing manual workarounds (like hand-made navmeshes) but I’m not sure if that’s necessarily any better in terms of resources.
You could use A* on very rough, lowpoly map that would be very fast to give you a direction and have your character start moving quickly. Then over the the time, you narrow the research by providing a more detailed map on which you perform your computations.
You could use Dijkstra and compute offline the shortest paths informations.
Or be creative, use both! The downside of the latter method is that it involves loads of memory while the first one is CPU-heavy. So why not try an hybrid solution?
On the iphone you will pretty surely not be able to avoid reducing the path calculation amount and optimize it considerably (like with any phone game)
That means:
Create a path network which is used for calculation. For anything that bases on realworld testing and environment evaluation
The iphone is pretty restricted in view and speed, so you will not move far in a given amount of time. Ensure to implement that time horizon knowledge with your solution. You don’t need to know stuff to their end, only the next few steps
As suggested above, storing some “common knowledge” will likely be a good thing for long range movement like the travel routes between important points.
A* is really cheap if you are using a low number of nodes. I am guessing your node requirements won’t be too bad for movement within a clickable area on the iPhone.
I suggest trying A* first. It’s something that you will find useful in other games, even if it doesn’t fit your speed requirements in this particular game. The other solutions are much less general and , this is just a guess, less straightforward to implement.
Thanks, yeah, it seems A* is the model with the most information out there. The geometry (for navigation purposes) will be kept extremely simple. It will mostly involve a character finding its way around furniture, up stairs, etc. So, it may also involve multiple levels of elevation (possibly overlapping) so I’m hoping I can find a system that supports that as well. I suppose I will have to create a layered system from one A* grid to another.
I’m just going to start with a simple room with a table in the middle, and see if I create a setup where the character intelligently goes around the table.
Do you guys think that “AgnryAnt’s” pathfinding system would be a good fit for this system? Will it work on the iPhone at this point? I wonder if there is an example of a basic A* system that I could dissect for now.
Can anybody recommend any books that cover pathfinding in a way a beginner could follow?
I made an A* function that uses a two-dimensional array for its position data, so it’s not automatically tied to object positions, and it’s very fast on the iPhone. I’d share it but I did it in Cocoa, not Unity, so it’s probably less helpful than any of these links:
It took a bit, but I was able to port this over to Unity. It’s undocumented and kind of tangled up in my game’s code, so I can’t post it right now (also, I only implemented the Manhattan-style search).
I just tried to get my A* script to compile with #pragma strict, and it’s a no-go. I’m almost finished with a project that isn’t using A*, so when I’m done with that I’ll try and make an iPhone version of the A* script.
This was one of the first things I did in Unity, so forgive the clumsiness. I could do this a lot cleaner in C# now.
These currently only work with Unity Standard. How it works:
Add a GameGrid2D and an AStar component to a GameObject. Then add another script that will actually fill the grid and store the path. That script should do something like this:
var entry : Vector2;
var exit : Vector2;
var mapSize : Vector2;
var grid;
var astar;
var path = new Array();
function Start() {
grid = GetComponent(GameGrid2D);
astar = GetComponent(AStar);
grid.CreateGrid(mapSize.x, mapSize.y);
// Fill the grid with junk
for (x = 0; x < mapSize.x; x++)
{
for (y = 0; y < mapSize.y; y++)
{
if (x == exit.x y == exit.y)
continue;
if (x == entry.x y == entry.y)
continue;
if (Random.value < 0.25)
{
grid.Set(x,y,1);
}
}
}
astar.Setup(grid, entry, exit);
path = astar.Path(); // if path.Length > 0 you have a valid path from entry to exit.
}
The path array contains a list of x,y positions that someone would walk in order to get from entry to exit.
The part you can now spend ages on is creating a GameGrid2D from objects you’ve placed in the world, or instantiating world objects based on the contents of the GameGrid2D. I had a helper function in my script called GridPosToWorldPos, which let me instantiate objects in the world based on an x,y position from the grid.
Pinging/Necro to see if anyone had any luck here. I stared at it for some time to no avail…tons of errors (in Unity iPhone) as silent said it only worked in Unity Standard.
Pinging/Necro to see if anyone had any luck here. I stared at it for some time to no avail…tons of errors (in Unity iPhone) as silent said it only worked in Unity Standard.
