A* Pathfinding Project

GraphUpdateScene Nonconvex vs Mutiple Game Obects, each with Convex


#1

I’m plotting some roads. I have to choose between using non-convex areas or using multiple game objects.

I suspect using a non convex shape would be much better than say 10 game objects each with their own GraphUpdateScene component with a convex shape.

Any thoughts on which is best?


#2

Hi

It depends on how much they overlap. The only difference between the convex and non-convex modes is that the convex one can use a slightly more optimized point-in-polygon test.

If you are doing roads, they are usually pretty long and windy. I would suggest splitting them up into chunks of some reasonable length and using the non-convex mode for those chunks. The cost of the graph update is roughly proportional to the number of nodes the axis aligned bounding box of the GraphUpdateScene component covers.


#3

Thanks Aron. Thats perfect.


#4

To add a small note. Each node in the axis aligned bounding box has to iterate through all the points in the graph update scene shape. So if you end up with a very large number of points there then performance will not be so good. That’s why I recommended splitting the road up into smaller parts if possible.


#5

This is our worst case scenario. I’ll just do it as convex, then keep an eye on performance as we progress. (We’re going to build out make of these hex tiles.)

Actually, I might try making a map with heaps of these lined up using convex, non convex and see if I can measure any time difference in the graph generation.

Quick Update: I did my tests and with 20 of these lined up a full Scan takes about 13 seconds and there was perhaps 0.1s difference between convex and non convex given our current tile / graph setup.


#6

Hi

How many points does each GraphUpdateScene contain in that case?


#7

I used 56 in that hex.


#8

Okay.

Btw. If you can, try the beta version (https://www.arongranberg.com/astar/download). It has much faster grid graph scanning.


#9

Yeah, we will check it out. We are only 2 months into a 2-3 year project. We’ll grab it when you release it.

Did you know we used A* on Void Bastards?


#10

Oh that’s cool! No I didn’t know that.
Looks like a really cool game!

That voice actor though… He reminds me so much of the narrator in the Stanley Parable XD
Is it the same guy? Or have you just happened to find someone that just sounds very much like him? :stuck_out_tongue:


#11

No thats him!

some extra text.


#12

really cool looking game! You really nailed the grudgy ness with the stylized art.
listening to a review it sounds quite well thought out and good replay ability.
Aron should link the survey to add your game to the main page :slight_smile: I can’t find it right now


#13

Haha. Cool!
He is a great voice actor.

Hey. Do you want me to add Void Bastards to the A* Package homepage? (https://arongranberg.com/astar/)?


#14

That would be cool! Yes Please!


#15

Hey also, I really love the polygon creation method you have on the GraphUpdateScene component. Is that something you created yourself, or did you pull it from somewhere.

We have to make some polygons in editor for the world map, and the current method we are using it much worse.

I was thinking we might check out pro-builder or some other middleware. But I really like the simplicity of your method.


#16

Nice! It’s added now. You may have to refresh the page a few times for it to show up (the 3 games that show up are randomly selected).

Thanks! It’s something I made myself. It’s not that much code, you can probably steal most of it from the GraphUpdateSceneEditor.cs script :stuck_out_tongue: