Those are actually options I'm looking into! I'm also looking into them for another project... anyhow.
There must be a more elegant way to do localization than simply brute-forcing an ~n^4 algorithm ala (currently):
map; //a larger, full-scale bitmap "map" from a game
viewport; //a subset of map of unknown location (x,y) but known dimensions (h,w)
4// (note all uses of w,h is solely viewport.wh)
every x in map
every y in map
every i in al_get_bitmap_width(
every j in al_get_bitmap_height(
i, y +
every pixel in rectangle i,j,w,h set matches rectangle x,y,w,h)goto
matched: //reported values from scan
Without the "if first pixel fails, abort" clause, it takes forever to run on at ~6000,6000 map matching a 320x200 box. Like, I let it run all night and it either had an bug or simply never finished in that time.
CUDA would speed this up insanely fast. But I still want to understand some proper/elegant localization methods.
Because this is phase 1.
Phase 2 =
Phase 3 = Profit.
(Just kidding.) Step 2 though is more complicated. Now, WITH NO WORLD MAP, do the same thing. Track movements of the screen. I actually have one semester of
graduate college experience with this... for 3-D stuff. Polygon stuff.
SLAM algorithms deal with this scenario:
Notice that's a polygonal representation. Detecting a hollow world. Like a shadow algorithm, or a polygonal fog-of-war algorithm. You COULD do it with tiles but the tiles are filled, or not filled.
My problem is really different than traditional SLAM. I'm not trying to "fill" something. I'm trying to notice landmarks on a completely-filled tile map. I could mark certain tiles as passable or not passable but I'm not doing pathfinding. I'm trying to say "here's a small picture or a puzzle piece, where does this piece fit into the puzzle if you already have the full puzzle completed." [and later, once pieces of the puzzle are missing.]
Also, for the minimap, that is actually something I'll support for "hinting". However, my program is not designed just for Starcraft and cannot rely solely on it. It's more of an optional feature (of which there may be more subtle useful features.)
But what I'm trying to do is work with:
1 - No insider data knowledge (like copying raw memory to get screen coordinates), only visual imagery AND an existing map. (To help tune algorithms.)
2 - Next step, working without an existing map and "filling it in" as I go.
Much how SLAM works, but again, I'm filling in flat pixels not walls. Perhaps that's not a helpful distinction. But in my head, that keeps popping up. That my question is at a 90 degree angle to normal SLAM. Like, I'm painting floors, and a 2-D SLAM algorithm is detecting walls.
Okay, like, if you had a camera pointed at the floor (or an optical mouse camera), and were driving a robot like a Roomba around, and you took your starting position to equal [0,0]. If you drove north, you would call that positive y axis. Looking SOLELY at the image input (and stored previous images) how do you tell whether your robot has moved forward/backward/etc.
One edge case I'll have to deal with eventually is "teleportation" (instead of scrolling, warping from one spot to another, like clicking on a minimap.)--whereas normal heuristics mean you're going to only likely move [VAR] amount from your last sampling point.
Another edge case will be, detecting a "map change" like an RPG game and you walk into a house and it's a map change. [Hmm, I could store suspected 'teleporters' so future jumps are expected when you get close to a teleporter.]
 Come to think of it, how do optical mice work!? Surely an algorithm exists and it's fast enough to run on embedded hardware!
 OPTICAL FLOW.
FINALLY. I found some keywords that may help me find suitable algorithms. Just for the heck of it, I tried to find a physical example to give you guys and lo and behold, trying to find you an example may have found me an applicable allegory to my problem.
 cleaned up code a bit.
 One more thing I'll have to do is re-enable that really slow version (not aborting early) and actually calculate a "cost" or "error" for every possible site, and select the lowest cost guess. Noting that for many tile games with "open fields" or large repeating areas... the first guess can actually be completely wrong. That is, multiple sites actually can be 100% pixel perfect. In that case, I think I'd select the closest-to-last-guessed site.
I've also considered doing the same exhaustive search (brute) but changing the search order so that it "spirals" out from the last known guess. Since most movements will be nearby, the first guess should be the valid one.
However, once we start involving less-than-perfect matches (like a player or unit moving around that isn't there) this is going to go from "exact matches" to "best heuristic guess" pretty damn fast.