Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pathfinding

juhrjuhr.itch.io

Post reply on HN
Print view View original

21–30 of 48 posts

Re: Pathfinding

#21

Post by stonemetal12 »

ninetyninenine wrote: post #14
blt wrote: post #11

Earlier quoted context omitted.

Sure, but in games sometimes improving the average case is less important than the worst case.

So you're saying everything always moves all the time so it's more efficient to just never check and have the algorithm assume something moved always.

No, if it takes 1 ms to check if things have moved, and 5 ms to do the pathfinding then the worst case is 6ms when something moves. A guarantied 5 makes for a more stable frame rate than a sometimes 1ms, sometimes 6ms calculation. Often times 60 FPS average with high variability feels worse than 30 FPS with low variability.

Re: Pathfinding

#22

Post by juhrjuhr »

Hello!

I'm the developer of this game. Thanks very much for your interest and discussion here :)

I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future.

The game I'm developing is a commercial project, so it would be silly to be on the front page of HN and not try to direct people towards the commercial side of things. Here is the link to the game's steam page, you can wishlist and maybe buy the game when it's released so I can afford living expenses and expensive coffee beans: https://store.steampowered.com/app/3656660/Deep_Space_Exploi...

Thank you! :)

Re: Pathfinding

#23

Post by juhrjuhr »

chrisdalke wrote: post #5

Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations. The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.

This definitely happens! Mostly it's from the NPC taking a corner a little too quickly when there's obstacles around. I've added data to the resulting path so that the NPC can know how far each path step is from an obstacle so that it can slow itself down first.

Like you said, it adds a lot to the fun so I'm only trying to smooth out those cases that look stupid.

Re: Pathfinding

#24

Post by juhrjuhr »

Sohcahtoa82 wrote: post #13

I'm surprised it takes several milliseconds to find a path. We've been using A* to find paths in games for over 20 years now. We did it on CPUs with speeds measured in Mhz. Higher clocks and architecture improvements mean we're a couple orders of magnitude faster. How is it that it takes so long to operate on modern hardware?

Hey, I'm the developer of the game in the blog post. What takes several milliseconds is the number of world queries that need to be made to detect blocking objects and also object proximity. This is why I went with a quad tree to try to speed that part of things up.

Once those queries have been made the actual search is very fast. The problem then is that those queries need to be made again due to the dynamic nature of the game world.

Re: Pathfinding

#25

Post by stefan_ »

Sohcahtoa82 wrote: post #13

I'm surprised it takes several milliseconds to find a path. We've been using A* to find paths in games for over 20 years now. We did it on CPUs with speeds measured in Mhz. Higher clocks and architecture improvements mean we're a couple orders of magnitude faster. How is it that it takes so long to operate on modern hardware?

You probably realized its absurd to have 50000 square nodes in your pathfinding graph and instead divided the area into 50 convex polygons (if that). Convex polygons being the basic shape because you can go directly from every point within to every other point within.

Re: Pathfinding

#26

Post by malux85 »

juhrjuhr wrote: post #22

Hello! I'm the developer of this game. Thanks very much for your interest and discussion here :) I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future. The game I'm developing is a commercial project, so it would be silly…

Great particle effects! Wishlisted and waiting!

Re: Pathfinding

#27

Post by tavianator »

juhrjuhr wrote: post #22

Hello! I'm the developer of this game. Thanks very much for your interest and discussion here :) I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future. The game I'm developing is a commercial project, so it would be silly…

You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.

Re: Pathfinding

#28

Post by johnh-hn »

chrisdalke wrote: post #5

Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations. The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.

Indeed. There is something satisfying about building these and watching them in full flow.

A couple of years ago, I completed a pathfinding assignment designed by David Churchill (https://www.cs.mun.ca/~dchurchill/) for his Algorithmic Techniques for AI course. I'm not a student, and only his students have access to the actual assignment files, so I made a faithful recreation of it by looking at slides he had on a video at the time. The assignment is about pathfinding on a 2D grid. That's fun enough, but I've wanted to put my own spin on it.

Over the past few weeks, I revisited this and applied it to real-world mapping data from OpenStreetMap instead. It uses OverPass API (https://dev.overpass-api.de/) to fetch the data, which is free to use. The data loading times can be a little unpredictable, especially for larger search areas, but I'm happy with it how it turned out. You can find it here if you're interested: https://johnh.co/projects/openstreetmap-pathfinding/

Re: Pathfinding

#29

Post by johnh-hn »

juhrjuhr wrote: post #22

Hello! I'm the developer of this game. Thanks very much for your interest and discussion here :) I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future. The game I'm developing is a commercial project, so it would be silly…

This is a cool concept. How long have you been working on it? And do you have a rough idea of when you'll release it?

Re: Pathfinding

#30

Post by porphyra »

stefan_ wrote: post #25
Sohcahtoa82 wrote: post #13

I'm surprised it takes several milliseconds to find a path. We've been using A* to find paths in games for over 20 years now. We did it on CPUs with speeds measured in Mhz. Higher clocks and architecture improvements mean we're a couple orders of magnitude faster. How is it that it takes so long to operate on modern hardware?

You probably realized its absurd to have 50000 square nodes in your pathfinding graph and instead divided the area into 50 convex polygons (if that). Convex polygons being the basic shape because you can go directly from every point within to every other point within.

Yeah generally you'd use a visibility graph/navmesh. I don't know why people keep trying to do path finding on a dense grid --- even with quadtree-based space partitioning, you might still end up with a complexity dependent on how far apart things are, rather than how many things there are.
Post reply on HN