# Pathfinding A* pathfind - shortcuts in gridbased-paths?

## Recommended Posts

That's good, I've mucked with units that are rectangular and have a turn radius.  It gets expensive very fast.

##### Share on other sites

Maybe your grid-based path calculation is the wrong approach? What if you convert the grid to navmesh, and then do continuous path computation?

Unfortunately, the above sentence is as far as my knowledge goes, I have no idea of implications if you take that approach.

##### Share on other sites

I agree that grid-based is the root of the problem here. I just assumed that he couldn't switch to navmesh for whatever reason.

## Create an account

Register a new account

• 11
• 9
• 16
• 16
• 10
• ### Similar Content

• Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
thanks
Jack

• There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (uastar.c and uastar.h) library: https://github.com/ferreiradaselva/uastar
No memory dynamic allocation. Straight to the point (the README.md explains how to use).
It's nothing biggie, but certainly useful.
Path finder at work:

I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).

• I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
Any ideas?
Jack

• Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.

The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer.

I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!

https://goo.gl/forms/S0etAlAAHL6S5kTI2
• By baabaa
Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
Any thoughts?