Raycasting
ID Software’s Wolfenstein 3D was the first game to produce a world with real-time texture mapping. The hardware it ran on is incredibly primitive by today’s standards; the algorithm is correspondingly simple. Raycasting, similar to raytracing, is the technique Wolfenstein 3D used.
For each column of pixels rendered, the engine traces the path of a ray from the camera's position until it hits something. Since Wolfenstein levels are all orthogonal (i.e., right angles only), this is easy enough for the computers of 1992 to perform thousands of times per second. Once a wall is hit, the game draws an entire column of pixels in the display at once by scaling the appropriate column of pixels in the texture.
This is why most games from this era stored textures in column major order, even though video memory is in row major order.
On the left is a diagram showing a player (red dot) in a level like those in Wolfenstein. The red lines are the rays. The white area is the part of the level that the player can see.