Amit was an instrumental part in the development of one of my favorite video games, Realm of the Mad God. It was a masterpiece of the Flash game genre, and its guild feature introduced me to many lifelong friends.
RotMG has a great idea that I wish more games would copy: difficulty scales with elevation. If you want to take it easy, stick to the coasts. If you want a challenge, strike inland towards the mountains (or follow a river upstream). It's a great way of intuitively expressing difficulty ranges across a sprawling world map, and I remember being disappointed the first time that I played Skyrim that it didn't seem to do the same.
One of the map design goals in RotMG was that players could start playing solo on the coasts, and then as they moved up towards the mountains, the area would shrink so they would be more likely to meet each other. However, when we added teleportation the "forcing function" wasn't needed anymore. Players naturally wanted to play with each other. Also, a lot more players were high level so we needed more mountain land and less coastal land. For https://gasgame.net/ we're using a different design, where south is easier and north is harder. Relative to RotMG's map it shrinks the beginner areas and expands the veteran areas.
I remember when I got back into programming, this site was one of the things that really made me excited to code + develop a deeper understanding of algorithms :)
speak of the devil! i've been putting together a little board game in Godot in my free time, and just finished devouring all of the hexagon content this week.
Amit's work is awesome! Right up there with Inigo Quillez's site on graphics in terms of informativeness and fascination in his own domain.
Off-topic a bit, but I've been curious about a 2D pathfinding problem for a while that this site doesn't seem to tackle despite having lots of articles on the subject. Is there an algorithm out there for finding "enclaves" (i.e. places where you might want to place rewards, spawn the player) within a large 2D terrain grid?
Not super precise, but given a 2D boolean array of pathable/unpathable cells, say generated by Perlin noise, find locations that are only accessible via a relatively narrow "choke point". Example: https://imgur.com/a/jFPXlS5
Standard pathfinding algorithms don't provide enough information to do this, but maybe there's some kind of heuristic approach that could work well.
Lots of pathfinding solutions prefer to work with connected convex polygons (since inside the polygon, you can always go straight to every other point inside). You could merge your cells into these polygons and then filter for small ones by area, I guess.
You are not trying to find a "path" since you don't have a starting point - you only have end points. Your enclaves are more defined by the shape of the walls (roughly x cells in radius) than with the fact that you reach them through chokepoints. After all, a chokepoint can be just a small door in an otherwise big corridor, separating two big areas. And by concentrating on chokepoints you will lose all the "isolated islands".
You might be luckier treating this as a "map treatment" problem. An algorithm that does things to the whole map, and then reads the result.
For example:
1. Start assigning a score of 0 to all map cells.
2. For every cell in the map, set to 1 if it's in contact with any walls
3. Then add 1 to every cell of the map if it contacts a cell with a non-zero value
4. Repeat the above step n times, where n is the average "radius" of you enclave rooms.
5. Every cell with a score of n or higher is a "candidate". For every candidate:
5.a Check that none of the cells around have a bigger score. If so, move on to the next candidate
5.b Check that there's no "treasure" around it in a circle of radius n
5.c You have found the center of an enclave. Mark it with "treasure" and move on to the next cell.
Find starting point in dungeon. A* to every room. Rooms with a large distance (iter count) and with only one or two paths out (choke points, use graph to see edges) become potentials, every potential that is _far & narrow_ is flagged “enclave” with rewards increasing by distance to start.
This is one way to approach the problem. The other way is to do prefab rooms and when generating your dungeons, randomly select one or two prefab enclave rooms to throw into the shuffle. Shuffle the rooms and spread them out then connect hallways and such. This is the approach that Enter the Gungeon took.
Another approach is what @otikik describes. Tracing the walls buy assigning a value to the cells that can then be scored. Minesweeper style.
Tarjan's Algorithm can be used to find choke points, although I haven't tried it myself [1]. I think what I would try is Breadth First Search with multiple start points to calculate various metrics for the map [2] and maybe All-Pairs if you need more [3]. For example, you might use Tarjan's or All-Pairs to find the most commonly used corridors, and then use Breadth First Search from those "central" points to find the "farthest from central corridor" points.
Likewise, Amit is phenomenal and the content (and especially its presentation) is really second to none. The value he places on ensuring links stay working, and that content is accurate and updated — is truly phenomenal and almost inconceivable these days.
I’ve also always enjoyed every (virtual) interaction I’ve had with him, however brief — and appreciate that he remembers me and the problems/challenges we faced in my games.
SimAirport and SimCasino very likely wouldn’t be the same (or would have taken much longer to achieve, at best) without his content.
Just a class act; one of these days I’d love to buy Amit a beer or a coffee. My invite doesn’t expire, perhaps next time you’re in the area! :)
Context: I had been planning to visit adanto6840 on a road trip planned for March 2020, but then … the pandemic hit and I had to cancel those plans. But one day I will take that road trip :-)
Playing around with a hex based game myself, the bookmark to the Hexagonal Grid is a constant companion over the years. It was updated slightly over the years with some visual cues. Amazing presentation, and so great to learn.
Apart from the excellent subject matter, I often pull up this site during UI/UX discussions. Amit clearly has the ability to do really advanced JavaScript visualizations, but he only uses it exactly when necessary. Most of it is a plain document like you might write in Markdown, but when he uses JavaScript, it's illuminating, connected to all the other examples, and clean. Any animation he uses is clearly initiated by the user, and is there not because it looks cool, but because the intermediate frames help the user understand what's happening. It also never moves the rest of the layout around. I go back to this site any time I'm pondering how to do good online documentation, interactive help, tutorials, or even text-heavy presentation of results.
100% agree! Bartosz Ciechanowski along with Amit Patel are national treasures. Their expository writing coupled with ChatGPT do dig into some of the more salient points has been a complete game charger for my self learning.
Thank you! I treat them as documents, with some interactive elements. I tend to avoid traditional animations because they're outside the reader's control. I want the reader to be able to pause, slow down, speed up, rewind, etc. One thing I'm going for but haven't completely achieved is that I want the diagrams to be useful even before the interaction.
I love this website! It was the place I've understood how A* is working in early 2010s when I started getting into more advanced "standalone" (w/o GameMaker/TGF) gamedev.
Am going to chime in as well - Amit is amazing and has been providing his knowledge and experience since the early 90's, when I first encountered him on FidoNet over BBS, then next on Usenet.
Agree - I was active enough on Usenet that at one point a book publisher sent me a box of books because apparently I had helped out one of their authors, and he asked them to do so. (Wiley FTW)
Amit is a treasure. I referenced his articles many times when making my own games. We could really use more thoughtful and friendly visual learning resources like this for other subject matter.
A fantastic site. When I originally took over teaching Intro to AI, I initially relied on the A* search closed/open set pseudocode explanation[1]. However, when it would come time to ask students to implement it, I was constantly finding students absolutely confused by the approach. Once I swapped over to Amit's A* explanation, the number of confused students dropped significantly. Forever thankful for their walkthrough.
Amit describes the differences here [2], but briefly:
- The Wiki pseduocode uses Set data structures for everything. While these are covered in classes, the up-tree concept isn't as heavily described as other trees
- Looking at it now, it looks like the pseudocode is a little more beginner friendly, but "back in mah day" it was not
- Although, RedBlob's pseudocode for obtaining neighboring nodes is clearer than "for each neighbor of current" (Wikipedia pseudocode)
- RedBlob uses Priority Queues and Maps instead of Sets, which connect better to other AI searches / recommendation algorithms. Higher 'priority' recommendations move to root in PQs while nodes in Sets... don't... they just sort of 'exist'
- The Maps make looking up node costs more intuitive than lists (aka "current := the node in openSet having the lowest fScore[] value")
1. I use words for variable names instead of single letters like the textbooks do. I use "priority" instead of "F", "cost_so_far" instead of "G", "heuristic" instead of "H", "cost" instead of "w", "frontier" instead of "OPEN" or "O", "visited" instead of "CLOSED" or "C", "current" instead of "u", "next" or "neighbor" instead of "v".
2. The textbooks use an "open" and "closed" set. But in code, these aren't explicitly stored in set data structures. Instead, they're implicit. The cost_so_far dict(map) contains as keys both the open and closed sets, and the frontier (priority queue) contains the open set. So in my explanation of A* I focus on these data structures (priority queue and dict) instead of the open/closed sets. And when I do talk about the sets, I talk about the combined open and closed sets, calling it "visited" or "reached", because it's the combined set that is actually in the data structures.
3. The textbooks use a priority queue with reprioritization. When you visit a node that has a lower cost than the previously found cost, you go into the priority queue and adjust the cost. In my presentation I don't use reprioritization. Instead, I insert another entry into the priority queue with the lower cost. This makes the priority queue simpler (reprioritization is complicated). And in practice, I think it's faster too.
I always wish there was more specification surrounding his Perlin noise algorithm he has on his website. For example, asking what the range of output values is does not have an easy answer.
In addition to range I'd like to see the distribution, especially with multiple octaves of noises added together. I haven't found a good page about that.
146 comments
[ 0.21 ms ] story [ 465 ms ] threadFor posterity, here's Amit on map generation: https://simblob.blogspot.com/2010/01/simple-map-generation.h...
Amit's work is awesome! Right up there with Inigo Quillez's site on graphics in terms of informativeness and fascination in his own domain.
Not super precise, but given a 2D boolean array of pathable/unpathable cells, say generated by Perlin noise, find locations that are only accessible via a relatively narrow "choke point". Example: https://imgur.com/a/jFPXlS5
Standard pathfinding algorithms don't provide enough information to do this, but maybe there's some kind of heuristic approach that could work well.
Choose random starting point and compute distance to all other points on the map. Repeat for multiple random starting points.
Average the distance.
Points with high average distance are difficult to reach.
You might be luckier treating this as a "map treatment" problem. An algorithm that does things to the whole map, and then reads the result.
For example:
This is one way to approach the problem. The other way is to do prefab rooms and when generating your dungeons, randomly select one or two prefab enclave rooms to throw into the shuffle. Shuffle the rooms and spread them out then connect hallways and such. This is the approach that Enter the Gungeon took.
Another approach is what @otikik describes. Tracing the walls buy assigning a value to the cells that can then be scored. Minesweeper style.
[1] https://old.reddit.com/r/roguelikedev/comments/dc4orn/identi...
[2] https://www.redblobgames.com/pathfinding/distance-to-any/
[3] https://www.redblobgames.com/pathfinding/all-pairs/
One of the seven evil hexes :D
I’ve also always enjoyed every (virtual) interaction I’ve had with him, however brief — and appreciate that he remembers me and the problems/challenges we faced in my games.
SimAirport and SimCasino very likely wouldn’t be the same (or would have taken much longer to achieve, at best) without his content.
Just a class act; one of these days I’d love to buy Amit a beer or a coffee. My invite doesn’t expire, perhaps next time you’re in the area! :)
I am collecting some of the design elements here: https://www.redblobgames.com/making-of/little-things/
Regular tech blog: https://amitp.blogspot.com/ Game Dev blog: https://simblob.blogspot.com/
[1] https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
- The Wiki pseduocode uses Set data structures for everything. While these are covered in classes, the up-tree concept isn't as heavily described as other trees
- Looking at it now, it looks like the pseudocode is a little more beginner friendly, but "back in mah day" it was not
- Although, RedBlob's pseudocode for obtaining neighboring nodes is clearer than "for each neighbor of current" (Wikipedia pseudocode)
- RedBlob uses Priority Queues and Maps instead of Sets, which connect better to other AI searches / recommendation algorithms. Higher 'priority' recommendations move to root in PQs while nodes in Sets... don't... they just sort of 'exist'
- The Maps make looking up node costs more intuitive than lists (aka "current := the node in openSet having the lowest fScore[] value")
[2] https://www.redblobgames.com/pathfinding/a-star/implementati...
2. The textbooks use an "open" and "closed" set. But in code, these aren't explicitly stored in set data structures. Instead, they're implicit. The cost_so_far dict(map) contains as keys both the open and closed sets, and the frontier (priority queue) contains the open set. So in my explanation of A* I focus on these data structures (priority queue and dict) instead of the open/closed sets. And when I do talk about the sets, I talk about the combined open and closed sets, calling it "visited" or "reached", because it's the combined set that is actually in the data structures.
3. The textbooks use a priority queue with reprioritization. When you visit a node that has a lower cost than the previously found cost, you go into the priority queue and adjust the cost. In my presentation I don't use reprioritization. Instead, I insert another entry into the priority queue with the lower cost. This makes the priority queue simpler (reprioritization is complicated). And in practice, I think it's faster too.
https://cs.nyu.edu/~perlin/
Yes, the Perlin noise guy among many other things.
In addition to range I'd like to see the distribution, especially with multiple octaves of noises added together. I haven't found a good page about that.