Need A* Help

[ArchAngel075]

Is there more stress involved when using diagonal pathfinding as opposed to (as you call it-) orthogonal pathfinding ?

In a test i have a 32*32 tile set using STI, i convert the 2D STI tiles to a format the astar uses, but ive noticed that if i ran the path = pathfind update every 1s between to locations on the map(very far away, lots of solid tiles in the way) I experience some frame drops, if i run it once its fine and if constant then id be better off doing a while(true) end loop if i wanted that much freeze.

[zorfmorf]

As I've written before, this specifc astar library doesn't take into account that finding neighbors in a grid is trivial (4-8 depending on whether you can walk diagonally). It looks at all tiles and checks for each on if it is a neighbor. (Which is totally fine if you're not working with a grid and even totally fine in most other cases).

However, for a 32x32 grid this shouldn't be a problem. Are you sure that you run it once per second and not once per update(dt) call?

[Zilarrezko]

Alright, So I had enough time to work on a quick one script. It's getting time to study for a final tomorrow and then graduation the next day. So I'm going to post this, I tried fixing this one for the past two hours or so, no luck though. Probably a grammatical somewhere.

You guys are probably getting pretty mad at me, as I'm not reading carefully through the posts as I really should. I just want to stretch a couple things out.

I want to not use an outside library as I want to learn inside and out the A* algorithm because I feel it will give me an insight to an area of AI that will benefit me and give me an advantage in future AI classes that I'll be taking sooner or later (hopefully soon). I can't grow if someone just hands me the code and it immediately works and I can derp around later, I'm not learning anything in that case and I'd very much like to just read something once and learn it immediately. Though I Have to see someone else do it and do it myself a few times before I learn it myself. That's one reason why I think the Jump Point search part will be difficult for me.

I plan on making this as messy in my mind in it's basic repetitive form so I can easily change things around not only in my head easier but also through your guys' recommendations and suggestions (If that makes sense, then something might be wrong because it most likely shouldn't). This is seen with my way to find neighbors (which I think is still my problem right now unfortunately) Though I've seen Roland had a more compact way.

One thing I'd like is a simplified explanation in the difference of heuristics. Which one is better in which cases?
Manhattan as I believe is just the row difference between the column difference, and I guess euclidean is just the literal distance between two points. But some would have a better use in other cases, right?

That's all I can think of right now. Ya guys must think I'm a total doof haha, I'm not really gettin' this but I'm tryin'. As for this code that I wrote, there's a couple things I forsee having trouble with. One will be optimization, Obviously over large distances it will lag, especially If I wrote it, so if anyone has any optimization quarks they can teach me for now and future reference that'd be epic. Another problem would I forsee myself is if the path is not found, I think the term is having "islands" where the start is unable to path to the goal. But other than those, and that neighbor problem (darn those neighbors!) I think I'm doing pretty well, and I'm happy with my progress, I'm not happy with how slow I'm progressing.

Have a good one, and I will check back in a couple days! happy LÖVE! (Sorry, this is probably severely boring to look at, I should add more pictures to make it more interesting.)

[zorfmorf]

I assume you mean the exception you get when calculating paths:

Code: Select all

Error: pathfind.lua:155: attempt to index a nil value

That is pretty easy to explain.

Code: Select all

...
if not nodes[y-1][x].collidable and nodes[y-1][x].parent == nil then
...

When checking neighbors, you are not checking if that neighbor node actually exists. For example, if y = 1 you are checking neighbor nodes[y-1][x], but as nodes[0] doesn't exist (it's nil) you run into this exception when trying to index it.

You have to change all your neighbor checks to validate the existence of the neighbor node. You know y,x are valid indices so you only need to do it for modified x and/or y.

Code: Select all

...
if not nodes[y-1] == nil and not nodes[y-1][x].collidable and nodes[y-1][x].parent == nil then
...
if not nodes[y][x+1] == nil and not nodes[y][x+1].collidable and nodes[y][x+1].parent == nil then
...

If you have several conditions as if condition, lua checks them from left to right and aborts as soon as one is not fulfilled. So the above code will work even for invalid indices.

[Roland_Yonaba]

Hi Zilarrezko,

I strongly encourage you to learn pathfinding on your own, it is a very interesting subject, and very learningful topic.
Noone said you should use a library. I just pointed out the fact that there are some code available that can serve as reference
for implementation.

The Great Zorfmorf already pinpointed the problem with your implementation. There are a few others, but you can focus on fixing the bugs first. I'll add a minor detail. Intead of checking :

Code: Select all

if a ~= nil then ...

A common Lua idiom, that I find nicer would be:

Code: Select all

if not a then

nil, as false is a falsy value in Lua. So the latter is identical to the former.

So, in case you want to check for a node, instead of

Code: Select all

if not nodes[y-1] == nil and not nodes[y-1][x].collidable and nodes[y-1][x].parent == nil then

This one would do the same.

Code: Select all

if nodes[y-1] and nodes[y-1][x].collidable and not nodes[y-1][x].parent then

I'd go for that, cause it looks nicer and much more readable to me.
Actually, I think you should also check for x:

Code: Select all

if nodes[y-1] and nodes[y-1][x] and nodes[y-1][x].collidable and not nodes[y-1][x].parent then

Second, about heuristics, I have already mentionned what I consider to be the most complete resource out there on heuristics for pathfinding, kindly written by the Great Amit Patel. I'll repost the link again: heuristics. Added to that, you can also play with the visual JS demo and try to see how heuristics affect the path found.

My last advice would be ditching Jump Point Search, for now. Take your time to fully understand Astar, in-depth, and related search algorithms such as Dijkstra, Best First, Depth First, Breadth First search algorithms. Jump Point Search will be easier to grasp then. The only advantage of this algorithm is the gain of speed on large open grids. But it has some fallbacks, as it is limited to grid with uniform costs, not weighted grids.

[davisdude]

Intead of checking :

Code: Select all

if a ~= nil then ...

A common Lua idiom, that I find nicer would be:

Code: Select all

if not a then

nil, as false is a falsy value in Lua. So the latter is identical to the former.

I think you meant:

Code: Select all

if a then

Since they're checking if it's not nil.