Depends on exactly what you want to have randomized...

You may need two programs (or halves of one program), the first which decides on the placement of the items you want linked, and returns the html to make the image map ie <MAP> tags, including a image tag which references the same or another perl script, telling it through cgi parameters how the items are set out. The second program can then draw the image (with GD) and return it to the client.

Another way instead of using <MAP> tags you can include an image as part of a cgi form and that cgi will recieve the x and y coordinates where the click occured and you can decide what to do based on those coordinates related to the contents of the image.

I've got a perl program which already does what I first described. If you really want I'll post it to snippets or something. But I really suggest you have a try at making it yourself.