Showing posts with label math. Show all posts
Showing posts with label math. Show all posts

Upgrading my PRNG for procedural generation #

For a long time now I've been using a very simple Park-Miller LCG random number generator for my procedural generation projects. This is in part because back in the Flash days, Michael Baczynski's "polygonal.de" library was popular, and it had an implementation of Park-Miller. When I switched to Haxe, I used his Haxe data structures library. And then when I switched to Javascript, I used the Javascript port of polygonal's library, and then I wrote my own. I love how simple the core algorithm is.

However I know that it's not a great random number generator.

The original Flash version and the Javascript port both point to Robin Whittle's page about this algorithm, which explained that 16807 was the original multiplier used in this random number generator, but that "47271 or 69621" would be better. I ended up making my own code that used 47271. But I noticed today that the Wikipedia page says 48271 is better, so I'm wondering if 47271 is a typo. So I looked at the paper and indeed, 48271 and 69621 are listed. Not 47271. So for years now I've been using a multiplier based on a typo.

Doh!

Read more »

Labels:

– Amit – Thursday, May 05, 2022 – 6 comments

Orbits of planets #

When I'm not feeling particularly inspired to work on a bigger project, I explore topics that might be useful later. I have been reading about planetary exploration, orbital mechanics, lunar chemistry, and other space topics. Along the way I found John Carlos Baez's blog post about the Pentagram of Venus. What a cool image! I wanted to try it myself. So I did.

Orbits of planetsOrbits of planets

Play with it yourself!

Labels:

– Amit – Monday, January 21, 2019 – 0 comments

Math explorables #

There are times when I'm on YouTube watching a math video that I think, “oh, that would be fun to play with!” What I should do is recreate the diagram in Desmos or Geogebra. But instead I just move on to another video. Recently I decided I should try making some diagrams, in part to improve my Javascript/web skills, but in part because it seemed like it'd be fun! So I did this for two math videos:

Mathologer multiplication on a circle
3Blue1Brown Feynman's Last Lecture

Both of these were quick, under an hour (mostly fiddling with colors, line widths, transparency, etc): an ellipse from line segments, multiplication with modulo on a circle.

Labels:

– Amit – Saturday, November 24, 2018 – 0 comments

Mapgen4: oblique projection #

One of my goals for mapgen4 was to explore non-realistic approaches, both to map generation and to map rendering. I wanted to explain the unusual projection I'm using.

For procedurally generated wilderness maps, it's very common to see a top-down view, often using colors to represent height or biomes:

Top-down view

It's simple to implement, especially in 2D, and it shows the areas of the map, including coastlines and rivers and lakes. You can see where the mountains are, but only because of the color and lighting.

Read more »

Labels: , , ,

– Amit – Wednesday, September 19, 2018 – 3 comments

Hex grids: simplifying the variants #

On the original hex grid guide I had claimed there were over 70 variants of hex grids. Most of these turn out to be merely a different choice of axes, either by renaming them or by negating the sign. Here are some variants of offset coordinates:

rename q and r offset axes

And here are some variants of axial coordinates:

rename q and r axial axes

Axial and Cube are really the same, except Cubes explicitly store the third coordinate and in Axial we calculate it in the accessor, when needed.

rename cube axes

Why would you want some of the other labelings? If I use an alternate labeling of offset coordinates, I can rotate the entire grid from pointy top to flat top and back:

rotate offset hex grid

This simplifies the math. It means I no longer need to treat pointy and flat top hexes separately, but instead I can focus on just a few basic grid types (cube, axial, even offset, odd offset) and then produce the pointy and flat top from those. I can further simplify by merging axial and cube together. I don't yet know if I want to do that. Can I merge even and odd offset? Yes, probably, but I think I won't right now.

parity-offset.png

Pointy top vs Flat top is a rotation. I had originally claimed it was a rotation of 30° but it is simpler to think of it as a rotation of 90°. It's even simpler to think of it as a permutation of x,y into y,x (renaming axes). There are also several coordinate systems that I don't cover on the page, and don't plan to anytime soon. However I might add a supplemental page that describes them.

I believe the new descriptions of coordinate systems will be simpler than the previous ones. However, they're also different, and I worry about changing the system that I've described in some incompatible way.

  1. Should I unify Axial and Cube?
  2. Even if I don't, should I rename Cube's coordinates from x,y,z to q,r,s? That way they match up more closely, and Cube is no longer confused with cartesian coordinates.
  3. Should I unify even Offset (even-q, even-r) and odd Offset (odd-q, odd-r)? I think the math is slightly uglier but it'd work just fine.
  4. Should I try to support all possible axis assignments, or just some "canonical" ones like I do now?
  5. Should I try to preserve the specific choices of axes on the current page, or choose the ones that make things simpler?

Update: [2015-03-28] I'm no longer convinced that swapping x,y is the easiest way to deal with pointy vs flat top. It's the simplest implementation, but it causes "q" and "r" to no longer correspond to "column" and "row", and I think it might be worth preserving that mnemonic. A 90° rotation is nice to implement too but I think the 30° rotation best preserves q/r.

Labels: , ,

– Amit – Sunday, March 22, 2015 – 0 comments

Prospect theory and utility functions #

(Note: I'm going to try writing more unpolished things on this blog and leave the polished articles to redblobgames.com.)

The utility functions I learned in economics are history-agnostic. They look at the current state of the world and calculate a “utility”. For example, you might say the utility of money is the logarithm of the amount of money you have.

Prospect Theory says that this view of the world does not match how people actually behave. Instead, the history of how you got to a certain point matters in how you value it. There's an asymmetry around a “reference point”:

Valuefun.jpg
(credit: Wikipedia, Prospect Theory page)

Consider these scenarios:

  • You get $200 and have a 90% chance of losing $100 of it.
  • You get $100 and have a 10% chance of gaining an additional $100.

These are mathematically equivalent. Both have a 90% chance of giving $100 and 10% chance of giving $200. However, they are not equivalent to humans. That's because humans consider not only the final result but how it was reached. Having $200 and then losing $100 feels different from having just the $100 in the first place. Even though the outcomes are the same, the reference point is different, so it feels different. Prospect theory takes this into account somewhat.

In game AI, I've only used regular utility functions. However, it seems reasonable to try using prospect theory in some way. Even prospect theory isn't complete; there are more human behaviors in decision making and valuation that it doesn't account for. Maybe FTT or something else. But sometimes you want to balance simplicity and comprehensiveness. In any case, it's something I'll want to ponder the next time I'm writing AI evaluation functions for NPCs.

Labels: , ,

– Amit – Thursday, May 22, 2014 – 3 comments

Notes on noise functions and map generation #

Over the summer I decided to study signal processing, with audio and music as potential applications. I should've realized that my brain would get back to maps somehow. I had been writing newbie-level notes for myself using emacs org-mode. Someone asked me about map generation, so I turned the signal processing notes into notes about map generation. Org-mode was really nice for writing notes. It let me mix notes and source code, and then I exported it all to HTML:

Notes on Noise Functions and Map Generation

Labels: , ,

– Amit – Sunday, September 01, 2013 – 0 comments

Guide to hexagonal grids #

A few weeks before Game Developers Conference, I thought to myself, what article can I write that’ll just take 2 weeks? I decided hexagonal grids, as a subset of my bigger article on all grids, would be a reasonable choice. I already have all the material; I've collected it for nearly 20 years on my site.

I was wrong.

Read more »

Labels: , ,

– Amit – Wednesday, May 08, 2013 – 2 comments

Curved Roads and Tracks #

I love city building and transportation games, and ever since I worked on one, I’ve had a side interest in how to represent and draw roads and railroad tracks. After playing lots of Cities XL, I started to wonder how I’d represent curved roads.

Roads and tracks in Cities in Motion
Read more »

Labels:

– Amit – Thursday, February 21, 2013 – 5 comments

2d Visibility #

For one of my projects I wanted to calculate the areas that are visible from the player. In a 2d top-down game or an isometric game you can calculate visibility and lighting in 2 dimensions and store it in a bitmap. As usual I got distracted by writing about the algorithm. I've spent too much time on writing it up so I'm going to publish it even though I'm not quite happy with the explanation. I can revise it later.

Here's the algorithm for 2d visibility along with a demo and source code.

Notes about the process

Part of what took a long time was going back and forth between the demo and the tutorial. The demo showed some concepts, then the tutorial tried to explain them. Then I realized that I'm missing some concepts and need to update the demo to show them. This took quite a bit of iteration.

A nice side effect of trying to explain the algorithm is that it helped me improve the algorithm. In an earlier version, sorting lines of different sizes didn't work well. It wasn't a problem in my project because all the lines were the same size, but in the demo it was an issue. While trying to explain this I found a better way to sort the lines so that it worked on all lengths. Another corner case that doesn't work well is when the lines intersect. This also doesn't happen in my project but it can happen in the demo. I decided the solution would complicate the demo code too much (I want it to be reasonably readable) so I instead detected those corner cases and marked them in the demo.

The other thing that took so long was that I kept rewriting the UI portion. The original version was for an isometric game, and used shaders to project the light map onto the 3d world. Next I wrote a Haxe + Canvas implementation to run as part of the article, but decided that I should write the UI in Javascript directly because I was more familiar with it. I kept the core algorithm in Haxe (shared with my Flash projects) and wrote the UI in Javascript + d3.js + SVG. It was easier to work with but it ran too slowly on the iPad, and as much as I love d3, this isn't a great fit. So I then wrote a JqueryUI + Canvas implementation. That too was slow but after learning more about Canvas I was able to speed it up to run reasonably on the iPad. I learned a lot by trying different languages and libraries; I hope not to spend several months on the next tutorial.

Other articles

After writing this for my project I decided to look around and see what other people have done. I didn't find a comprehensive survey of techniques but there are several interesting techniques out there. Here's the raw list from my notes; I haven't spent the time to categorize or evaluate them (sorry!). I've also added to the list after posting my page.

Labels: ,

– Amit – Thursday, July 05, 2012 – 1 comment

Tutorial: probability and damage rolls #

I’ve been interested in interactive diagrams for a while now, and started playing making illustrations with HTML5. I’ve written a tutorial on using randomness for damage rolls. Implementation notes:

  • I’m using Mike Bostock’s D3.js + SVG for the diagrams.
  • I’m using Bret Victor’s Tangle library for diagram parameters.
  • You can drag the parameters around to change the diagrams. The idea is that you can edit the parameters in the sample code, and see the diagram update too.
  • The draggable numbers from Tangle work on the iPad too.
  • Most (all?) Android and Touchpad browsers don’t support SVG. :-( (Maybe I should’ve used Canvas)
  • Older versions of Internet Explorer don’t support SVG. :-(
  • I designed the page to reformat itself for mobile browsers, narrow browsers, and wide browsers. I used CSS media queries for reformatting the text, but unfortunately had to use Javascript for redrawing the diagrams.
  • Red Blob Games is where I’ll be placing my new tutorials and articles, instead of my Stanford alumni account.

At some point I’d like to go back to my existing articles and update them with interactive diagrams. I’m just not yet sure where they might be useful instead of gimmicky. I’d also like to write a tutorial about random loot drops.

Labels: ,

– Amit – Sunday, January 22, 2012 – 0 comments

Distances on a triangular grid #

As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:

The first coordinate (which I will call u) is the position along the horizontal axis; the second (which I call v) is the position along the southwest/northeast diagonal. The Left/Right parity introduces some compliation; I let R be 1 and L be 0. This coordinate system is nice for storing maps in an array, but it's not as clean, because triangle grids have three axes but only two of them are expressed in the coordinates. For the horizontal axis I used 2u+R as the position; for the second axis I used 2v+R. I guessed that the position along the third axis would u-v. I drew some grids on paper, wrote down the u,v values, and then computed the three positional values. They behave properly for computing distances along the third axis, but the system falls apart when computing distances not on the three axes.

Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:

Coordinate system for triangles

I want to map the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where exactly one of a,b,c changes when you cross a line. Here's where I decided to use algebra. In u,v,R space, the black triangle has coordinates 0,0,0; the triangle to the east of it has coordinates 0,0,1; to the west, -1,0,1; to the south, 0,-1,1. In a,b,c space, the black triangle is 0,0,0; the east triangle is 0,0,1; the west triangle is 0,-1,0; and the south triangle is -1,0,0.

I want a formula that computes a, and I expect it to be linear, so I write a = au*u + av*v + aR*R + constant. That's four unknowns, but we know the constant will be 0, so it's really three unknowns. To get three equations, I plug in the values for the east, west, and south triangles, then solve for the coefficients. Let's see what happens: 

  For each s in (a, b, c), and each triangle i:
  si = su*u + sv*v + sR*R

  East triangle: u,v,R = 0,0,1
  s1 = su*0 + sv*0 + sR*1
  therefore: sR = s1
  
  West triangle: u,v,R = -1,0,1
  s2 = su*-1 + sv*0 + sR*1
  therefore: su = sR - s2
  
  South triangle: u,v,R = 0,-1,1
  s3 = su*0 + sv*-1 + sR*1
  therefore: sv = sR - s3

When s is axis a, we look at a for triangles 1 (east), 2 (west), and 3 (south), so a1 is 0, a2 is 0, and a3 is -1. The algebra tells us that aR = 0, au = 0, and av = 1. That means the formula is a = v. Pretty simple. Doing the same for b and c, I get b = u and c = u + v + R.

These results are simple enough that if I played with the grid enough, I would have come up with them. However the algebraic approach works for other constraints, not only the simple ones. I also used it to create a coordinate system with 2u+v+R, u+2v+R, v-u (this is 30 degrees rotated from the one above), which may be useful for other algorithms. Algebra and calculus also come in handy for defining movements (e.g., splines), growth rates, equilibria in interacting systems, and other types of interesting behaviors in games.

What is the distance between two locations in a triangular grid? Each step involves a line crossing, and we want to count steps, so we add up the line crossings along each axis (a, b, c): distance = abs(Δu) + abs(Δv) + abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.

Labels: , ,

– Amit – Tuesday, June 19, 2007 – 5 comments
Subscribe to: Comments ( Atom )