I understand the concerns, but the same "have you tried implementing" concern applies there too. This is premature optimization, until you do it both ways and profile it and see if the runtime difference matters. Cache locality is a thing, but so is prematurely guessing about cache locality.
Not everything using A* runs millions of pathfinding queries in tight loops. Maybe it's an offline turn-based game that runs A* once per move and saving 10 μs just won't ever matter as compared to the complexity cost of implementing and maintaining the extra abstraction.
While I appreciate your concern about premature optimization, having 2D arrays as fundamental data structures in this kind of thing is so common that it just seems bizarre that you even call it an optimization. The resulting code is just as simple and natural, after all.
Perhaps we need a countering meme about gratuitous de-optimization...
Not everything using A* runs millions of pathfinding queries in tight loops. Maybe it's an offline turn-based game that runs A* once per move and saving 10 μs just won't ever matter as compared to the complexity cost of implementing and maintaining the extra abstraction.