amitp

22 ms·

1. 181.▲
   by amitp 11y ago

   A* runs faster if you have better path cost estimates. To get the shortest paths, you want an estimate that's as close to the true cost, but not greater than it. You can precalculate to generate good estimates. Traffic makes the costs
2. 182.▲
   by amitp 11y ago

   Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http:&#
3. 183.▲
   by amitp 11y ago

   Sorry about that. What I meant by "any number of ways" is that the way I generate elevations works on any shape of coastline. In the demo, the default is to generate the coastline the way you describe — Perlin noise minus distance
4. 184.▲
   by amitp 12y ago

   The offset approach is what most people do. I've used it too. It makes the storage simpler for rectangle shaped maps but the algorithms more complicated (and slower). I wrote this page to present the alternative coordinate systems. The
5. 185.▲
   by amitp 12y ago

   Thanks! (I'm actually in the middle of a major update to the page — I hope to have it published in a few weeks) I used d3.js for this page (and most of the pages on my site). For a given shape of map (rectangular, triangular, hexagonal
6. 186.▲
   by amitp 12y ago

   One nice thing about linear interpolation is that the same algorithm works for 2D grids, 3D grids, and hex grids. For 3D, the diagonal_distance, point_lerp, and point_round functions can look at at z in addition to x and y. For hex grids, y
7. 187.▲
   by amitp 12y ago

   I used to draw the lines that way, but I've switched to drawing the squares instead. It tends to look cleaner, the code is simpler, and it also lets me color the squares individually. If I really need to draw the lines, I can set a bac
8. 188.▲
   by amitp 12y ago

   We seem to perceive it in something closer to hsl space (3d) than rgb space (also 3d). You can tell that it's "purple" but you can also tell whether it's saturated or not, and if it's bright or dark purple. Also che
9. 189.▲
   by amitp 12y ago

   Another cool algorithm animation site: http://rosulek.github.io/vamonos/demos/ uses Vamonos ( http://rosulek.github.io/vamonos/ ). However, it looks like you have to write the algorithm twice,
10. 190.▲
    by amitp 12y ago

    Yep. I wrote SRE, and then wrote a game engine (modem communication, bbs interface, logins, menus, inter-bbs communication, ansi color, etc.) so that Mehul could write AC6 and BRE. He continued writing games (see http://en.wikipe
11. 191.▲
    by amitp 12y ago

    Seeing my game programming bookmarks page up on HN is unexpected. :) Yes, I started it a very long time ago (most likely 1994 but that's before Wayback Machine, and I don't have my own archive). I should update the links on that p
12. 192.▲
    by amitp 12y ago

    Yes. Frustrating bug. I ended up compiling my own, but I think the newer pretests have the fix. If you want to build your own pretest with the "Yamamoto Mitsuharu" version of Emacs (railwaycat), I posted the commands I ran: http:
13. 193.▲
    by amitp 12y ago

    Ah, thanks! I've been focusing on simplicity rather than performance, but deque is just as simple here, so I should use it. :-)
14. 194.▲
    by amitp 12y ago

    A* is typically for single source, single destination. For crowds, if you have lots of agents that want to go to a single destination, you can often use Breadth First Search or Dijkstra's Algorithm. That tutsplus article uses Breadth F
15. 195.▲
    by amitp 12y ago

    I love that page! I link to it from my own semi-outdated page: http://theory.stanford.edu/~amitp/GameProgramming/Implementa...
16. 196.▲
    by amitp 12y ago

    Thanks!
17. 197.▲
    by amitp 12y ago

    You're welcome! I do change the design every few years. The earliest one on Wayback Machine is https://web.archive.org/web/19981202094104/http://theory.sta...
18. 198.▲
    by amitp 12y ago

    (author here) I agree! I'm planning to reorder everything; see https://twitter.com/redblobgames/status/410182845777195008/p... for my current plan. The choice of heuristic is near the end of the new flow
19. 199.▲
    by amitp 12y ago

    Thanks! I use d3.js + SVG for most of the interactive ones. SVG makes it easy for me to attach mouse events to the elements in the diagram, and d3.js makes it easy for me to create, remove, and animate the elements individually. For the tow
20. 200.▲
    by amitp 12y ago

    There's not even much about admissibility (which is not always used in game settings). I don't have a good sense for consistency/monotonicity. Do you have an example of an inconsistent admissible heuristic?
21. 201.▲
    by amitp 12y ago

    Another way of looking at it: A* is Dijkstra where the edge weights have been modified. http://11011110.livejournal.com/135302.html
22. 202.▲
    by amitp 12y ago

    (author here) I wrote most of these notes in 1997 while working on a game. Little did I realize that it'd be one of my most popular web pages. The diagrams are colorful but I don't like them ( http://simblob.blogspot.com