You could work with blocks (x,y,w,h) instead of lines. Then, you could create patterns of walls as different objects. You could create a default Wall class that has all the basic information of each block (With x, y, w, h, etc). Then, you could create the different patterns:

class WallType1(Wall): ...

?class WallType2(Wall): ...

?class WallType3(Wall): ...

Each one of them could store the blocks in their different raw positions in a list or array, and the whole walltype (With their different blocks) could be moved just by setting the x and y.
Then, you could procedurally generate their positions for each map and create unpredictable mazes at each game.

The free-blocks would be just positions, like the walls, but they would comprise no walls, so, you could filter them with a "if not in wall-positions" logic, and allow the player and the ghosts to walk only through them. Concerning the AI, I think it would be a lot easier to think about once you have the free blocks.

You could procedurally generate just "lines of blocks", alternating randomly between horizontal and vertical wall-lines, but that would give you a much more randomic maze than the ones of the video. So that's why I've recommented the pattern-wall-objects (Groups of wall-blocks that can be randomly positioned at the creation of the level). I've made an algorithm that procedurally generates mazes for my game, and a more simplified version is available on Khan Academy.

Check it out and see if it inspires you:

https://www.khanacademy.org/cs/procedural-maze-generation-with-camera-translation-and-minimap/6384329197355008