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.
Need A* Help
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
Re: Need A* Help
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?
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
- Party member
- Posts: 345
- Joined: Mon Dec 10, 2012 5:50 am
- Location: Oregon
Re: Need A* Help
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.)
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.)
- 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 90 times
Re: Need A* Help
I assume you mean the exception you get when calculating paths:
That is pretty easy to explain.
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.
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.
Code: Select all
Error: pathfind.lua:155: attempt to index a nil value
Code: Select all
...
if not nodes[y-1][x].collidable and nodes[y-1][x].parent == nil then
...
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
...
- Roland_Yonaba
- Inner party member
- Posts: 1563
- Joined: Tue Jun 21, 2011 6:08 pm
- Location: Ouagadougou (Burkina Faso)
- Contact:
Re: Need A* Help
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 :
A common Lua idiom, that I find nicer would be:
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
This one would do the same.
I'd go for that, cause it looks nicer and much more readable to me.
Actually, I think you should also check for x:
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.
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 ...
Code: Select all
if not a then
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
Code: Select all
if nodes[y-1] and nodes[y-1][x].collidable and not nodes[y-1][x].parent then
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
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.
Re: Need A* Help
I think you meant:Roland_Yonaba wrote:Intead of checking :
A common Lua idiom, that I find nicer would be:Code: Select all
if a ~= nil then ...
nil, as false is a falsy value in Lua. So the latter is identical to the former.Code: Select all
if not a then
Code: Select all
if a then
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
Who is online
Users browsing this forum: Ahrefs [Bot] and 5 guests