Hacker News new | past | comments | ask | show | jobs | submit login

And if you pathfind on the visibility graph of those polygons' vertices, your path is even optimal in Euclidean space. Granted, that's a slightly larger graph, but still much smaller than all the grid cells.

And actually, depending on the connectivity of the fine square grid, pathfinding on it is pretty suboptimal too, because you're only finding paths that are shortest in Manhattan- or 8-connected distance (barring some fast-marching/Eikonal thing). If your units are really restricted to those motions then that's correct, but if they can move continuously then you're losing a lot of diagonals. So that's another argument for polygons.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: