Ok, I'm pretty sure 3D Monster Maze (1981) used an autotile system -albiet a very very different sort, that made 3d-looking tiles appear in the correct place.

Ok, I'm pretty sure 3D Monster Maze (1981) used an autotile system -albiet a very very different sort, that made 3d-looking tiles appear in the correct place. Is that a proper autotiler? I don't know, but the principle is pretty much the same. Anyway I'll bet there are old games still that are out there with auto-tiles.