2 ms·
The basic sin here is doing pathfinding around a million square cells just because that happens to be the base of your rendering. You merge it all into convex p
by stefan_ 4y ago
The basic sin here is doing pathfinding around a million square cells just because that happens to be the base of your rendering. You merge it all into convex polygons and suddenly the pathfinding is a pen&paper homework problem because theres about 5 of those left.
- substation13 4y agoMost classic RTS games have you place buildings on a grid. The buildings block movement so are important for pathing. You could merge large squares of open space as an optimization though.
- FooBarBizBazz 4y agoAnd 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.
- qikInNdOutReply 4y agohttps://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/Quadtree actually