I am making a 2d tile based game in Java, and I was wondering what the best way to store items in the world was. In the past i have always used an array the same size of the world but I want to make really big worlds, and I know for a fact this would be a bad idea. So I was just wondering what the best way would be?
If you define the type of your tiles e.g. by an int, you could use one bit of it to indicates if there is an item. The item itself you store in a List ordered by x coordinates (and if the x coordinate is the same, than use the y coordinate as second ordering property).
This way you can detect, if there is an item on the tile very fast (O(1) and than search in the List<Item> only if there is an item. On the list you can use binary search (first related to the x coordinate, and within the sublist of all items with the same x coordinate use binary search for the wanted y coordinate) O(log(n)) [n = number of items].
If you want to save memory, I would consider using an elementar data type to specify the tile (e.g. an int) and store your world e.g. in an int[][].