Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Are Allegro routines thread safe, and if so, which?

This thread is locked; no one can reply to it. rss feed Print
Are Allegro routines thread safe, and if so, which?
Chris Katko
Member #1,881
January 2002
avatar

(I didn't want to off-topic the other guys thread anymore so here's a new thread:)

You can easily multithread a for loop with a one-liner pragma using openMP:

int thread_count=8;
#pragma omp parallel for num_threads(thread_count)
for(int i=1;i<100000;i++)
    {
    do_work(i,record);
    }

see here

If I'm only reading from a bitmap, can I read using multiple threads at once? There is no theoretical hazard occurring (except maybe some cache contention) ala read-write-read. I'm JUST scanning a bitmap trying to find a match--more akin to machine learning / AI / image processing than a typical game usage.

I know OpenGL is single-threaded (which is why Vulkan was designed from the ground up to be multi-threaded--because they expect multi-GPU solutions to be required for hitting 6K/8K and higher.) And OpenGL is the one fetching textures. So I don't know where the line is. If I lock a bitmap, it gets sent to memory. But how fast is that memory, and can it be read multi-threaded? OR, would it be faster to scan every pixel and "convert" it to a simple integer array and then divy it up. However, this needs to be real-time. So would a full image conversion could add much latency? It might be faster to force the locked bitmap to be in a easily accessable format so I can do:

if(allegro_bitmap[31][512].r == 124){do something}

Instead of converting texture -> locked memory bitmap -> integer array. Just have texture -> locked memory bitmap with direct access.

I'm simply trying to read some pixels here. So, I'd appreciate some insight on what aspects of Allegro should and shouldn't be tampered with by a multi-threaded program.

Side rant: I would call OpenMP and this case more "batch job dispatch" than "multi-threaded" (which kind of implies to most people multiple, macro threads acting as separate modules that live the life of the program as opposed to tons of dispatched worker threads that come and go.)

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs

Edgar Reynaldo
Member #8,592
May 2007
avatar

Mutexes are for making concurrent access safe by serializing it. If you're not writing to the memory, you don't need a mutex. Allegro provides you a memory copy of the video bitmap when you use al_lock_bitmap. If you're reading and writing in chunks per thread, that's still safe, because the threads aren't messing with each other's data.

Use as many threads as you want, but I don't see what it's going to get you in this case.

What are you really trying to do here? You've kind of left that part out of your description of the problem.

Chris Katko
Member #1,881
January 2002
avatar

I am scanning a large tilemap and attempting to match it to a subset map, to determine it's location.

Right now I'm just brute forcing it and it's fast ish considering it's running on my netbook and the images are large. Eventually I'm going to add landmark detection and other heuristic means but I don't have the experience with them and can't seem to find the right keywords. SLAM, simultaneous localization and mapping, is what I'm working toward but all articles and algorithms deal with polygonal structures. I'm working with tiles and sprites. The world is at a 90 degree angle.

Basicially, imagine you wanted to make a bot play Starcraft. How would your bot tell where it is on the map? It seems existing bot apis rip the screen coordinates from memory. But what if you had to do it with only access to the screen image?

[Edit] god this phones keyboard sucks.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs

Edgar Reynaldo
Member #8,592
May 2007
avatar

Polybios
Member #12,293
October 2010

Why not use CUDA or something like OpenCL (only know its name) to do it directly on the GPU?

Chris Katko
Member #1,881
January 2002
avatar

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):

#SelectExpand
1//from memory 2ALLEGRO_BITMAP *map; //a larger, full-scale bitmap "map" from a game 3ALLEGRO_BITMAP *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) 5 6for every x in map 7 for every y in map 8 fail: 9 for every i in al_get_bitmap_width(viewport) 10 for every j in al_get_bitmap_height(viewport) 11 if(viewport[i,j].rgb != map[x + i, y + j].rgb)goto fail; 12 13 if(every pixel in rectangle i,j,w,h set matches rectangle x,y,w,h)goto matched; 14 15matched: //reported values from scan 16found_x = x; 17found_y = y;

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:

{"name":"a07fig14.gif","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/9\/398c6583e423a1b407a6e077081b3319.gif","w":373,"h":384,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/9\/398c6583e423a1b407a6e077081b3319"}a07fig14.gif

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.)

{"name":"latest","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79381cbd407ebecc87ba428230295e6a.jpg","w":675,"h":900,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79381cbd407ebecc87ba428230295e6a"}latest

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.]

[edit] Come to think of it, how do optical mice work!? Surely an algorithm exists and it's fast enough to run on embedded hardware!

[edit] OPTICAL FLOW.

https://en.wikipedia.org/wiki/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.

[edit] cleaned up code a bit.

[edit] 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.

{"name":"K-spaceStrategy_Spirals.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/d\/0d152e190ff0bca8b3a91f348d2c2f75.jpg","w":551,"h":282,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/d\/0d152e190ff0bca8b3a91f348d2c2f75"}K-spaceStrategy_Spirals.jpg

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.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs

SiegeLord
Member #7,827
October 2006
avatar

Unfortunately you need to look at source to tell what's thread safe and what's not. Some things are mutexed, but not all.

For your use case, you'll want to lock the bitmap, and then using al_get_pixel will be thread safe. If you don't lock it, it won't be thread safe.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Audric
Member #907
January 2001

Have you considered using a pixel shader ? If I understand correctly, it would be automatically called for every pixel of your texture, and you would code it to return "found / not_found" for this particular set of coordinates.
It would perform all the searches even when one is successful, however it would benefit from the parallel processing of the video card.

Go to: