Fun Fact: Regelmäßige Ziegelsteine gab es auch schon vor der Industriellen Zeit. Schon das alte Babylon war aus Lehmziegeln erbaut und gebrannte Ziegel waren auch schon bekannt. Siehe das Ischtar Tor.
Im Mittelalter gab es ab dem 12. Jhd. Backsteinromanik und später entsprechend auch Gotik und Renaissance. Für regelmäßige Steine muss man sich ja nur eine Form aus 4 Brettern zusammennageln und in einer Region mit ausreichend Lehm und Brennholz leben.
Das passt natürlich nicht so in das gängige Bild vom Mittelalter und wir sind ja bei Fantasy, aber historisch wäre es nicht unbedingt falsch. Vielleicht eher etwas, was Zwerge machen würden, wenn keine Felsen in ausreichender Größe vorhanden sind.