Rick's b.log - 2024/12/22
It is the 28th of December 2024 You are 18.220.196.68, pleased to meet you!

Big Town

But earlier in the week, my little car had performed miserably when the morning temperature was at freezing. It took damn-near a quarter of the battery to get to work, never mind make it back. And that was with running the heater for only three minutes to clear off the screen. Yes, it was pretty chilly, I wore gloves. Sadly it seems that when you need the heat is when the battery is the crappiest.
In addition to all of that, it seemed like I had to dump so much more power into the motor to get the car to move. Stagnant going up hills, needed a fair bit of oomph on the flat... I'm just guessing everything is notably stiffer in the cold.

So I gave myself two red lines. I'm British, we Brits love our red lines.

The first was if I wake up and it's less than 8°C, forget about it. I got up at six and made tea and fed kitty and it was four and a half. Oh well, went back to bed.

Got up again at half past ten. I had been awake for a while, but was mindlessly doomscrolling the "AITA" junk ripped from Reddit. But, alas, used tea needed out. So I dealt with that and looked at my webserver to see what the temperature was.

It was 8.1°C.

Right, that's it then. I'm going. I grabbed my phone, then grabbed the other one for the extended playlist, sorted out the cold box and shopping bags, then locked everything up and...

...was about eight kilometres down the road when I remembered that I hadn't yet shaved. Oh well, I can rock the George Michael look. Actually, given the state of my hair, it's more a "crazy dude who would blow up Earth for the lulz" look.

I had also neglected to realise that it was actually the last Saturday before Christmas. As such, the main roads were extremely busy. And there's me trundling along at about 47kph (a smidgen under 30mph) with a long queue of traffic behind. To their credit, nobody flashed their lights, nobody honked. Yes, I've had both, plus random people shouting "Putain!" out their window at me, as if driving this slow is something I'm doing on purpose just to piss everybody off and really there's this extra gear beyond 'D' that gets me up to 80kph like a real car...

My second red line was that I didn't want the battery to go lower than the 3/4 mark. This would be about a third of the battery in real terms, and I know here to the big Leclerc is about the same as a commute to work and back, plus I didn't need headlights so there shouldn't be any extra load. I would be willing to let it slip a tad below three quarters, but only a tad, as I needed charge for driving around town to the places I wanted to go plus enough to see me home safely. My car cannot be towed, it needs to be put on a flatbed (the manual is very clear about this), so getting myself towed home would be extra complications that I didn't need.
So if I wasn't anywhere near Big Town when the meter hit three quarters, sorry, tough luck, I'm turning around.

This... was the meter at the supermarket car park.

I can't believe how bang on this was.

As it was twice as long as going to work, it was twice as long driving - nearly forty minutes. And a lot more hair-raising as about two fifths of the journey is done on main roads. Aaargh!

At the supermarket, I put my headphones on and selected a suitably gothic playlist. Then just ambled around looking at everything. It's a pretty big supermarket so it has plenty of stuff mine doesn't. Including Heinz ketchup! Has Système U fallen out with Heinz or something? There's exactly zero bottles of it at my usual supermarket. Just some own brand and a Frenchie brand called Amora. They may be perfectly good, but I grew up with Heinz and it's what I put on my chips and, thanks, but in my life I have encountered plenty of "it's trying to be ketchup but doesn't quite hit the mark" red sauces. If I'm eating out, I don't have much choice. If I'm eating at home, Heinz dammit.

I picked up two bottles of Sarsons. The type with the screw cap and not the drip-shaker top, but I figure I could see how the drip-shaker comes off to refill the smaller curvy bottles.

The next grab was Blonvilliers organic cane sugar. I've been using the Daddy brand (it's what my local stocks) in my tea and it's sweet but it's just not the same. I got five bags, that ought to do me for a few months.

Just on a whim I also got a stick of sugar cane. Like, actual cane that the sugar comes from. I'm... not sure what I'm supposed to do with it.

I hadn't yet found any calendars on Amazon. Well, I lie, I found a fairly nice Wednesday one, but for some reason it was classed as a book so I either needed to pay €3 for postage or have it delivered to a place that sells books. Which claimed to be my local supermarket (they do sell books) but when I selected it as the delivery location decided that, actually, nope, they aren't going to deliver there. I can, instead, go to an Amazon locker (which doesn't sell books?) in another town to pick it up. Swipey-swipey delete. Sorry, no deal.
At the Leclerc I found a "witches flowers" calendar. Well, that'll do.

In the car park were four charging stations. Two are Type C (the three phase) and two are Type C (three phase) and Type E (wall socket). It looks like it may be possible to start charging and pay using a browser? I'm not sure, but I didn't need it so I didn't try.
The website suggests that the first 30 minutes of a charge are free, followed by €0,30/kWh. That sounds suspiciously subsidised, given that my home's bill estimation is €0,35/kWh.
The gotcha for little cars like mine is that after two hours of charging, it'll hit me for €1,20 per quarter hour. The payment will be automatically authorised to €50, and finalised once charging is complete...which is better than the €149 the petrol pumps would sucker you for.
I've never bought petrol from an automatic pump in the UK so I don't know if it is similar, but here in France as soon as you do your bank card in the machine, it'll immediately debit €149 (petrol) or €50 (this thing) and when the final amount is known, the difference will be handed back. This does not happen immediately, and may take several days (although it shouldn't). It's pretty crap behaviour if you ask me, but that's just how it is.
Many years ago when my bank card had stricter limits on what my card would allow per day, I tried to fill up at one pump but it wasn't working. I got a receipt for a debit of €0. When I tried it in the next pump over, my card was rejected because shopping earlier followed by €149 twice was simply more than the daily allowance.
I think my card now has a much higher limit that is calculated as "not more than X over any seven days" rather than "x per day" because, well, typically you're going to spend money more on one day than all days (like, when you go shopping) and back then the limits for standard cards were rather severe, like €300. I'd have needed to contact the bank to buy a washing machine, which is patently ridiculous...

My next stop was to Action where I found a cheap and cheerful dustbin with a slide-up lid for eight euros something. My current dustbin functions but it's old and crappy. I had a look in the supermarket. I had a look in the big Leclerc in Bain when I went to get my car seen to. There were plenty of suitable bins with unsuitable prices. We're looking at €35 as a minimum, and going up from there. I can buy a Pi for less. I can buy a proper meal out (non-fast food) for two for less. It's a bit ridiculous.
So when I saw a bin for that price at Action, I bought it. I mean, it's a bin for Christ's sake, its entire job in life is to stand in the corner with a bag inside and catch the teabags that I fling in its general direction.

"Adulting" is getting excited over a dustbin.

From there I stopped at Picard and, given that I have a freezer now, I think my purchases were actually quite restrained. Well, Picard isn't cheap, but then that's not their market. People who want cheap frozen stuff go to Lidl...

From there I ignored burger royalty and came home. Again with plenty of traffic behind me. Oh well.

As a bonus photo, I saw this at Action. While it makes sense to have corrected "A partir du" (as of...) to "Depuis le" (since the...), I wonder if this sign has really been kicking around for a decade. Maybe somebody just downloaded the thing and tossed it to the printer without fixing it and/or looking for an up to date one?

Recycling an old sign? Or printed anew without fixing it first?

The maths of raycasting - part one

So what we're going to do today is to pull the maths apart and instead of simply "doing what Lode did", we'll work through this bit by bit for full clarity.

This will use code presented in BBC BASIC; but it ought to be fairly simple to do the calculations in a different language like Lua or Python, or even a scientific calculator!

The first thing to know is that raycasting is not 3D. It is simply reading through some sort of two-dimensional map to create the illusion of 3D.

For our purposes, we shall be using the following map:

The pawns represent "walls", and the knight is the player's position. Because the board is marked in chess notation, we shall assume that A is 1, B is 2, and so on along the horizontal (x) co-ordinate.

Things we need to know

From this point on, co-ordinates will always be given in pairs, in the form x,y so I'll simply write that the player is at 4.5, 1.5.

In addition to the player's position, we also need to know their angle. This determines what way they are facing. Zero degrees in our grid is facing to the right, and sweeping anticlockwise, so ninety degrees is up.

Finally, we need to know the field of view (FOV) of the screen. This determines what the player can actually see on the screen. To small a field of fiew and everything will appear stretched and distorted. Too large a field of view and everything will appear squished and distorted. For a normal squarish display, a field of view of about 60° is about right. Obviously it'll be larger (say, 75°) for a widescreen display.

The field of view is calculated very simply by adding half to the angle the player is facing. Here is the above photo, this time the player's direction has been overlaid in magenta, and the boundaries of the field of view are shown as dashed green lines.

Since our field is 60°, we simply add half of that (30°) to the direction the player is facing. This gives us a starting angle of 120°. From there, when drawing the display, we simply sweep across subtracting the sixty degrees of our field of view.
For drawing the display, we only need to know the player's angle at the start to work out where to begin drawing the walls.

Raycasting in a nutshell

What this means is that we break the screen into vertical columns, and draw each one in turn from left to right.

You have by now, I am sure, guessed that how this actually works is to follow the path of a single 'ray' through the map until we reach a square that contains a 'wall'.

There are three ways that we could perform this calculation. The first is, once we know the angles we need to step through the grid, simply add a little (like 0.1) each time. This would work, but it would be unacceptably slow.
The second option is to add a larger increment. This would be faster, but do you see the black square directly in front of the player? The extremes of the field of view barely cross it. So if our increment was too large we'd skip right on through and not even notice if there's a wall there.

The third option, well, that's where the magic happens. ☺

Now, let's not get ahead of ourselves. Before we can go merrily skipping through the grid, we're going to need to change our angle (120°) into something that we can actually use with a two-dimensional grid. For instance, looking at it visually, it looks as though the x co-ordinate of where we cross into the black square is about 4.1,2.0... so how on earth do we translate the current player's position of 4.5, 1.5 into that?

Now comes the icky maths bit

We need to know a few more things. We need to know the current ray position.
We need to know the normalised direction vector of the ray (nerd-speak for "what way is it pointing?").
And finally, we need to calculate deltas. This tells you how much distance is needed to cross a square boundary.

The first thing we need to do is translate the ray angle into radians. The use of 0° to 360° is nice for humans, but not so great for mathematics.

PRINT RAD(120)
2.0943951

To determine the x direction vector, we use cosine. To determine the y direction vector, we use sine.

angle = RAD(120)
xdir = COS(angle)
ydir = SIN(angle)

This gives us direction vectors of x=-0.5 and y=0.866025404

For what it is worth, doing this on a fancy scientific calculator could be more trouble than it is worth.
I switched mine to radians and then entered 120°, with the key to convert that to radians. Did it? Yeah, it told me that it was 2π over 3. Uhh... So then I entered sin( 2π over 3 ) and it gave back the result of the square root of 2 over 3. This is all completely correct, but it's perhaps the most bloody obnoxious way of writing the result possible. Maybe maths people prefer looking at an equation rather than the actual answer...?

Oh, and don't ask how sine and cosine work. That's way above my pay grade. This may help.

From this, we can calculate the deltas as follows:

xdelta = ABS(1 / xdir)
ydelta = ABS(1 / ydir)

This gives us the values of x=2 and y=1.15470054. This says how far you must travel to get to the next square border. It is calculated by dividing from 1 to turn the direction into an increment.
It is worth mentioning that one should trap if the direction vector is zero and if it is, then set the delta to a large value, large enough that it won't ever be stepped into. This is for those times when the vector travels straight up, straight down, straight left or straight right.

What you need to know about the deltas is that it isn't a value that will step from one boundary to the next. It is, instead, a value of how many squares in the other coordinate need to be stepped in order for that ray to transition from one square to the next.

This is to say, the x delta is 2, which means that for x to step once, the ray must move through exactly two squares in the y direction.
This diagram demonstrates this, look at the positions of the two cyan arrows and notice that to go back from one square to the next in the x sense, it goes up two squares.

Now we have some values that we can work with, we can start plugging them into the grid.

If xdir is less than zero, then xstep is -1, otherwise it is 1. This means we either step to the left or to the right.
It's the same for ydir, to give us stepping up or down.

The final thing we need to do is set up our start position. For this, we take our offset into the current square and multiply it by the delta for the x and y sides.
It is done like this as the calculation depends upon whether it's a positive or negative.

IF ( xdir < 0 ) THEN
  xstep = -1
  xside = (xpos - xmap) * xdelta
ELSE
  xstep = 1
  xside = ((xmap + 1) - xpos) * xdelta
ENDIF

IF ( ydir < 0 ) THEN
  ystep = -1
  yside = (ypos - ymap) * ydelta
ELSE
  ystep = 1
  yside = ((ymap + 1) - ypos) * ydelta
ENDIF

Now that we have all of this information set up, we simply step through the grid dealing with whichever side is the closest.

IF ( xside < yside ) THEN
  xside += xdelta
  xmap += xstep
  side% = 0
ELSE
  yside += ydelta
  ymap += ystep
  side% = 1
ENDIF

As we fall out of this, we simply need to look at the map using xmap,ymap as an index to see if there's anything there. If there is, we can stop, otherwise we loop around again.

Notice that we are also setting side%. This is firstly because it is necessary in order to tell what we should be using to calculate the distance to the wall, and also because the algorithm can tell us, for free, if we hit the wall that's top/bottom or the one that is left/right. This allows us the opportunity to use some cheap effects to colour the two differently, like one being shaded. It's unrealistic as light doesn't work like that, but it's computationally free and it helps to add variety to the display to guide the player as to what direction they are facing. Having all of the walls looking the same is... actually pretty naff.

Some code to see this in action

playx = 4.5
playy = 1.5

DIM map%(8,8)
FOR a% = 1 TO 8
  FOR b% = 1 TO 8
    map%(a%, b%) = ASC(".")
  NEXT
NEXT

REPEAT
  INPUT "Angle (degrees) ";angdeg
  angle = RAD(angdeg)

  xpos = playx
  ypos = playy

  xdir = COS(angle)
  ydir = SIN(angle)

  IF ( xdir = 0 ) THEN
    xdelta = 123456
  ELSE
    xdelta = ABS(1 / xdir)
  ENDIF

  IF ( ydir = 0 ) THEN
    ydelta = 123456
  ELSE
    ydelta = ABS(1 / ydir)
  ENDIF

  xmap = INT(xpos)
  ymap = INT(ypos)

  PRINT "Ray position : ",xpos,", ",ypos
  PRINT "map position : ",xmap,", ",ymap
  PRINT "   direction : ",xdir,", ",ydir
  PRINT "       delta : ",xdelta,", ",ydelta

  IF ( xdir < 0 ) THEN
    xstep = -1
    xside = (xpos - xmap) * xdelta
  ELSE
    xstep = 1
    xside = ((xmap + 1) - xpos) * xdelta
  ENDIF

  IF ( ydir < 0 ) THEN
    ystep = -1
    yside = (ypos - ymap) * ydelta
  ELSE
    ystep = 1
    yside = ((ymap + 1) - ypos) * ydelta
  ENDIF

  PRINT "       sides : ",xside,", ",yside
  PRINT "        step : ",xstep,", ",ystep

  PRINT "Stepping through eight times:"
  PRINT "  [up (90°) should be 4,2; 4,3; 4,4, 4,5, etc]"
  PRINT "  [fov left (120°)... 4,2; 3,2; 3,3, 3,4, etc]"

  FOR a% = 1 TO 8
    FOR b% = 1 TO 8
      map%(a%, b%) = ASC(".")
    NEXT
  NEXT

  FOR loop% = 1 TO 8
    IF ( xside < yside ) THEN
      PRINT "               xside closest"
      xside += xdelta
      xmap += xstep
      side% = 0
    ELSE
      PRINT "               yside closest"
      yside += ydelta
      ymap += ystep
      side% = 1
    ENDIF
    PRINT "       sides : ",xside,", ",yside
    PRINT "         map : "+STR$(xmap)+", "+STR$(ymap)

    REM This is broken into two IFs for the blog
    IF ( (xmap > 0 ) AND ( xmap < 9 ) ) THEN
      IF ( (ymap > 0 ) AND ( ymap < 9 ) ) THEN
        map%(xmap, ymap) = loop% + 48 : REM What step is it?
      ENDIF
    ENDIF
  NEXT

  map%(playx,playy) = ASC("X") : REM The player position

  REM This is plotted 'weird' so it visually
  REM matches the photo of the chessboard.
  FOR a% = 8 TO 1 STEP -1
    FOR b% = 1 TO 8
      PRINT CHR$(map%(b%, a%))+" ";
    NEXT
    PRINT
  NEXT

UNTIL FALSE

It is intentionally verbose so you can see what happens every step of the way, creating an output that is full of scary numbers until you associate what the numbers mean with what is going on.
In the DDA, we step exactly eight times. A proper raycaster would have data in the grid and would step until something had been hit, but this means more code and I wanted to keep this simple.

Angle (degrees) ?120
Ray position :             4.5,                1.5
map position :               4,                  1
   direction :            -0.5,         0.866025404
       delta :               2,         1.15470054
       sides :               1,         0.577350269
        step :              -1,                  1
Stepping through three times:
  [up (90°) should be 4,2; 4,3; 4,4, 4,5, 4,6, etc]
  [fov left (120°)... 4,2; 3,2; 3,3, 3,4, 2,4, etc]
               yside closest
       sides :               1,         1.73205081
         map : 4, 2
               xside closest
       sides :               3,         1.73205081
         map : 3, 2
               yside closest
       sides :               3,         2.88675135
         map : 3, 3
               yside closest
       sides :               3,         4.04145188
         map : 3, 4
               xside closest
       sides :               5,         4.04145188
         map : 2, 4
               yside closest
       sides :               5,         5.19615242
         map : 2, 5
               xside closest
       sides :               7,         5.19615242
         map : 1, 5
               yside closest
       sides :               7,         6.35085296
         map : 1, 6
. . . . . . . . 
. . . . . . . . 
8 . . . . . . . 
7 6 . . . . . . 
. 5 4 . . . . . 
. . 3 . . . . . 
. . 2 1 . . . . 
. . . X . . . . 
Angle (degrees) ?

Now let's overlay this onto the chessboard so it all makes sense.

As it happens, we would never make it to the eighth position as there's a pawn at position seven representing a wall. This means that in a proper raycaster the DDA would stop here noting that a wall had been hit.

In the second part, we'll look at calculating the distance and working out how to actually draw the walls.

Your comments:

Gavin Wraith, 23rd December 2024, 00:09

> Maybe maths people prefer looking at an equation rather than the actual answer...?    By 'the actual answer' I presume you mean the numerical values? In which case the answer to the maybe is "you bet they do". A symbolic expression can tell humans (well mathematicians perhaps) what it means, whereas the numeric value is merely what the computer needs. When Deep Thought announced the answer to be 42, it should have said "the largest number of sides that a regular polygonal floor tile can have". See the difference?

David Pilling, 23rd December 2024, 19:21

"the most bloody obnoxious way of writing the result possible" - yeah but the exact value. If you're doing A level Maths you're expected to pick out these special values. Like tangent of 45 degrees is 1. Sin 30 is a half and so on. To an extent it is because problems usually have these values as answers. In real life your values might be nothing like them.

Rob, 23rd December 2024, 20:22

Pay-at-pump here used to pre-auth some silly amount, but all the ones I've used lately do some sort of check with the bank and say ok, you can spend up to <available funds amount>. Then just debits you that at the end. I don't know if they pre-auth it, but I've never had an issue with it reserving too much. Not have I tried spending the money between putting my card in the machine and finishing filling, to test it..