I am looking for performance gains out of my 2D tile game.
How should I store a layered map? A three dimensional array? I am currently using an Array List of objects containing matrices.
Much like in C, arrays are Evil, generally speaking, unless accesses to those objects occur so often that you can't afford a dynamic array (which should never be the case with a tile-map). And even if normal arrays are a necessary evil, multi-dimensional ones are Evil-er, where the "er" adds as much Evil as there are dimensions. I'd almost never use a plain old 3d array under any circumstances - I can think of maybe one or two edge cases, and I don't think a tile map is one of them.
I assume you're adding a matrix to your array list for each height level, right? That sounds about right...
Where do I store the array determining what is walkable and what isn't? Or should my 3 dimensional matrix contain objects that have this property (like they do now). Is this incredibly slow?
It depends how you do it, but it shouldn't be too bad.
The main thing is my game is running fast but not completely smooth. This is not due to graphics but due to loading additional tiles when the map shifts. The lag is barely noticeable, but it shouldn't be there for such simple a game.
Have you profiled? I can't see how...well, pretty much anything
about the way you store your tile map, apart from how you deal with the graphics, could conceivably become a bottleneck, unless you're running some fantastically complicated algorithms over your tiles. There just aren't enough tiles to make anything that you're doing per-tile become important, again, except for graphics, since there you may have thousands of pixels per tile.
When you say it's due to loading additional tiles, do you mean you're actually calling out to the disk to open/decompress/process graphics files, or are you just creating a new tile object?
One possibility occurs to me - are you copying everything in your matrix every time it shifts? Even this shouldn't be a huge deal if your tile map is a reasonable size, but is it possible you're doing something really inefficient there, like actually copying the sprite pixels over or something?
In any case, I think we may need to see some more information or (better) code to figure out what might be slowing you down. A layered tile map should have very little overhead apart from graphics.
What is the best way to do a time step for a game without physics or simulation by a time step variable? Consider a simulate() method that can only run forward 1 step in game time.
What exactly does your game need to do each step? It's hard to give advice without knowing what the specific requirements are, or even the type of game.