For the map structure, it can be the same as a typical top-down maze or dungeon game (similar to a rougelike game). Each map cell represents a feature (open space, wall, well, chest, etc.), like each square on a piece of graph paper.
Some old school games represented walls as divisions between cells (the lines between squares on graph paper), so you can have thin walls separating two cells. This is a bit harder to implement, and it doesn't look like the linked video uses this method.
There are basically 2 ways to go about drawing this, the truly old school way and to fake it using modern techniques.
For the old school approach, each feature (wall, door, chest) that appears at a certain location in the player's view needs is pre drawn on a sprite sheet. Perspective needs to be baked into the assets. It gets a bit complicated working out the walls in particular, probably need to work it out on piece of graph paper. Here is an example "template" where the player is at * and looking north, each number/letter is a wall cell in the player's field of view:
When drawing a view, you will need to take the player location and facing direction and build a list of walls and features in the view, then draw them in the order of the template. You will also need to have a static list of coordinates to know what and where to draw each wall sprite, depending on where it is in the player's view. As a made up example:
This might mean that if wall "A" needs to be drawn, copy a rectangular region from the sprite sheet at position 100,50, size 80,160 to screen position 0,20. Drawing them in order (1,2,... D, E) and using transparency on the sprites allows use of the painter's algorithm.
This works fine but is a bit tedious to implement (especially creating the wall sprites and getting them to line up in a pleasing way). That said, I've implemented such system a couple times and had fun doing it.
The other approach, which can be easier to implement (depending on your skill set) and much more extendable, is to fake it using 3D triangles. Going this route means you just need to have a texture for the walls. Field of view, lighting, animating movement and turning, fog - all these things are massively easier to add or tweak if using modern techniques.