4 ms·

A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.

• dahart 3y ago
  > pixel base solutions are naive. Why, and what do you mean, and what are the alternatives? Pixels are just the search space and may have nothing to do with the sophistication level of the search algorithm, no? In the case of simple 2d games that can run on retro hardware, searching over pixels may be the best thing to do with limited memory and limited cycles, it’s why they often do collision detection on pixels as well.
  • Arch485 3y ago
    If every tile in the game ("tile" being some discrete unit of walkable/not walkable) is 8px by 8px, then you're doing 64x the work you need to. The tile data will also be stored somewhere anyways to handle player collisions etc. (except in cases where memory is _extremely_ limited, but those are rare - in that case pixel data is used, as you suggested)
    • dahart 3y ago
      True, but if players and AI and game elements can move in units of pixels, and exist in multiple tiles at once, the it may be difficult to work in units of tiles. Not clear the parent was distinguishing between pixels and tiles too, or if the ‘naive’ comment was aimed at any kind of gridding, or something else.
  • moffkalast 3y ago
    Voronoi graphs are a fast option to get you in the approximate area, then a fine grid can do the last-mile part if need be. It does require preprocessing the map first though.