• Create Account

# A Star Pathfinding

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1Oliverr  Members   -  Reputation: 100

Like
0Likes
Like

Posted 16 November 2011 - 12:01 PM

Hi,

i am some what finishing on my implementation of A Star, tho i have some issues with some principles i believe. It works well with regural obstacles, but once there is concave obstacle it sometimes gives error, but always fills in the the space in the concave obstacle then moves to the goal. So its of course far from best path.

Here are few pics from working pathfinding :

and here is the problem :

i am not sure how to handle this problem. What i came to undersand is that i should probably compare for each node that is in closed list ( the final path nodes ) the path to that node from start. And if the g distance is smaller i should replace the path to this node with the new path. Tho i am not sure if thats what would help. Also when i was trying something like this it made the script too expensive as of course the path is computed for each node, instead just for one goal.
I was thinking if there was some easier solution for this, maybe based on f distance.

Thanks for any kind of help or suggestions. ( btw i am using javascript and Unity )

### #2IADaveMark  Moderators   -  Reputation: 2059

Like
0Likes
Like

Posted 16 November 2011 - 12:09 PM

You sure you aren't over-estimating your heuristic?
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #3SimonH  Members   -  Reputation: 133

Like
0Likes
Like

Posted 16 November 2011 - 12:15 PM

Sure you should check any neighbouring nodes from the closed list to see if your current path is shorter - that should solve that 'pooling' problem in image 3.
If your maps are all as simple as this you may find that fuzzy navigation is good enough and much cheaper!
Stickmen Wars 2 is in development.
Meanwhile try Bloodridge

### #4Oliverr  Members   -  Reputation: 100

Like
0Likes
Like

Posted 16 November 2011 - 01:59 PM

You sure you aren't over-estimating your heuristic?

I believe not, i am using standard heuristics for diagonal grid, so it shouldnt be problem. Anyway if you know about some issue concerning heuristicsk, please let me know.

### #5Oliverr  Members   -  Reputation: 100

Like
0Likes
Like

Posted 16 November 2011 - 02:03 PM

Sure you should check any neighbouring nodes from the closed list to see if your current path is shorter - that should solve that 'pooling' problem in image 3.
If your maps are all as simple as this you may find that fuzzy navigation is good enough and much cheaper!

It would be great, if i could somehow just create shortest path from the nodes in closed list, tho i am not sure how to check which path is shortest in this pooling scenario. I would realy like to avoid computing new path for each node. It will be used in quite big maps and if theres 500 nodes long path, it would mean to run check on 500 nodes, so it would be 500 times more expensive than its now :/

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS