LCD 40x4 też specjalnie duży nie jest, Twój labirynt będzie bardziej przypominał korytarz w Ikei lub innym supermarkecie.

Ale do celów edukacyjnych chyba wystarczy.
Wracając do procka. Na podłączenie wyświetlacza potrzebujesz 7 lub 11 pinów, sterowanie - lewo, prawo, góra, dół, start, ewentualnie reset - powiedzmy 6 pinów. Razem - 17 lub 13. Powinien wystarczyć nawet jakiś ATTiny. Żeby mieć trochę swobody i nie patrzeć na zbliżający się koniec pamięci, proponuję jakiś ATMega, najlepiej ATMega16 lub większy, bo one mają już obsługę JTAG-a, który bardzo pomaga uruchamiać prototypy.
W następnym kroku potrzebujesz uruchomić wyświetlacz poprzez wypisanie czegokolwiek. Potem już tylko ułożyć algorytm, który proponuję zacząć od konstrukcji tablicy odzwierciedlającej stan wyświetlacza. Taką tablicę możesz co pewien okres czasu (np. 100 ms) przepisywać w całości na wyświetlacz.