Need A* Help

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
ArchAngel075
Party member
Posts: 317
Joined: Mon Jun 24, 2013 5:16 am

Re: Need A* Help

Post by 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.
User avatar
zorfmorf
Prole
Posts: 33
Joined: Sat Mar 10, 2012 12:31 pm

Re: Need A* Help

Post by 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?
User avatar
Zilarrezko
Party member
Posts: 345
Joined: Mon Dec 10, 2012 5:50 am
Location: Oregon

Re: Need A* Help

Post by 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! :D (Sorry, this is probably severely boring to look at, I should add more pictures to make it more interesting.)
Attachments
workspace.love
For some reason the problem seems to be in the second while in the while loop and not in the check for current node.
(4.5 KiB) Downloaded 46 times
User avatar
zorfmorf
Prole
Posts: 33
Joined: Sat Mar 10, 2012 12:31 pm

Re: Need A* Help

Post by 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.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Need A* Help

Post by 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
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Need A* Help

Post by davisdude »

Roland_Yonaba wrote: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.
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
Post Reply

Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 17 guests