Function to check plan

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • KeredDrahcir
    Contributor
    • Nov 2009
    • 426

    Function to check plan

    I'm creating an application that allow the user to draw out a floor plan. It gives them a 12 x 8 grid and lets them click up to 50 sqaures. It stops them when they get to 50 but they can click on an already selected sqaure to turn it blank and then choose another.

    What I need to be able to do is check the plan. They can't have any gaps in it. All squares have the accesable from all other square on only in the four main directions (no diagonals).

    Is there some kind of function that could image a man standing in square one and making sure he can visit all the other squares.

    I'm willing to use php or JavaScript if required. Is there anything already around that will do that, or would somebody be able to assist me.

    There code for creating the floor plan is below.
    Code:
    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    
    <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    
      <head>
        <title>Plan</title>
        <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/>
        <script type="text/javascript">
    	<!--
    	  var count=0;
    
    	  function plan(id)
    	  {
    	    var obj = document.getElementById(id);
    
    	    if(obj.style.backgroundColor == "rgb(0, 0, 0)")
    	    {
    	      if(count <= 49)
    	      {
    	        count++;
    	      }
    	      else
    	      {
     		    alert('You can have a maximum of 50');
    	        count++;
              }
    	    }
    	    else if(obj.style.backgroundColor == "rgb(255, 0, 0)")
    	    {
    	      count--;
    	    }
    	    if(count <= 50)
    	    {
    		  obj.style.backgroundColor = (obj.style.backgroundColor == "rgb(0, 0, 0)") ? "#ff0000" : "#000000";
    		  obj.style.color = (obj.style.backgroundColor == "rgb(0, 0, 0)") ? "#000000" : "#ffffff";
    		}
    		if (count>50)
    		{
    	        count--;
    	    }
    	  }
    
    	  function number()
    	  {
    	    var room_number=0;
    	    col=0;
    	    row="a";
    	    for (var i=1; i<97; i++)
    	    {
    	      col++;
    	      if (i<97)
    		  {
    		    row="h";
    		  }
    		  if (i<85)
    		  {
    		    row="g";
    		  }
    		  if (i<73)
    		  {
    		    row="f";
    		  }
    		  if (i<61)
    		  {
    		    row="e";
    		  }
    		  if (i<49)
    		  {
    		    row="d";
    		  }
    		  if (i<37)
    		  {
    		    row="c";
    		  }
    		  if (i<25)
    		  {
    		    row="b";
    		  }
    		  if (i<13)
    		  {
    		    row="a";
              }
    
              if (col>12)
              {
                col=1;
              }
    	      var room = document.getElementById(row+col);
    		  if (room.style.backgroundColor == "rgb(255, 0, 0)")
    	      {
    	        room_number++;
    	        room.textContent=room_number;
    	      }
    	      else
    	      {
    	        room.textContent="";
    	      }
    	    }
    	  }
    	//-->
        </script>
      </head>
    
      <body style="background-color: #000000; width: 386px; margin: 10px auto 0;">
    <?php
        $l=0;
        $j=0;
    
        for ($i=0; $i<96; $i++)
        {
          $l++;
          $j++;
          if ($j<97)
          {
            $letter=h;
          }
          if ($j<85)
          {
            $letter=g;
          }
          if ($j<73)
          {
            $letter=f;
          }
          if ($j<61)
          {
            $letter=e;
          }
          if ($j<49)
          {
            $letter=d;
          }
          if ($j<37)
          {
            $letter=c;
          }
          if ($j<25)
          {
            $letter=b;
          }
          if ($j<13)
          {
            $letter=a;
          }
    
          if ($l>12)
          {
            $l=1;
          }
          $border="2px 0 0 2px";
          if ($l==12)
          {
            $border="2px 2px 0 2px";
          }
          if ($j>84)
    	  {
    	    $border="2px 0 2px 2px";
          }
          if ($j==96)
    	  {
    	  	$border="2px 2px 2px 2px";
          }
    ?>
          <div style="width: 30px; height: 30px; line-height: 30px; border-style: solid; border-color: #ffffff; border-width: <?=$border;?>; float: left; background-color: #000000; color: #ffffff; text-align: center; vertical-align: middle; font-weight: 700;" id="<?=$letter, $l;?>" onclick="plan('<?=$letter, $l;?>');">&nbsp;</div>
    <?php
        }
    ?>
        <input type="button" value="Done" onclick="number();"/>
      </body>
    </html>
  • Rabbit
    Recognized Expert MVP
    • Jan 2007
    • 12517

    #2
    Loop through every box and if it is an "active box" check the north, south, east, and west, boxes for at least one active box.

    Comment

    • KeredDrahcir
      Contributor
      • Nov 2009
      • 426

      #3
      I thought about that but found that if there could you have two groups of four boxes not connected. Someone did this once and I'm not sure how but this was 30 years ago on the computers of that day!

      Comment

      • Rabbit
        Recognized Expert MVP
        • Jan 2007
        • 12517

        #4
        In that case, you want to find the first "active" box and use a recursive algorithm to traverse all the connected boxes. Use an array to keep track of the traversed boxes. Then compare the traversal array to the original boxes to see if any "active" boxes have not been traversed.

        This way, only one group can ever be traversed.

        Comment

        • KeredDrahcir
          Contributor
          • Nov 2009
          • 426

          #5
          That's the idea. I was just wondering if someone could start me off because I'm not quite what way to go around it.
          It's not quite as simple on some plans. Would it help if included a plan that does work that I've used but would be very tricky to validate?

          Comment

          • Rabbit
            Recognized Expert MVP
            • Jan 2007
            • 12517

            #6
            It wouldn't hurt to have an example.

            In pseudo-code, the traversal would look like this:
            Code:
            function isValid() {
               for each box
                  if box is active
                     traverse box
                     exit for
            
               for each box
                  if box is active and not traversed
                     return fail
            
               return pass
            }  
            
            function traverse(box) {
               mark box as traversed in traversal array
            
               if north box is active and not traversed
                  traverse north box
               
               if east box is active and not traversed
                  traverse east box
            
               if south box is active and not traversed
                  traverse south box
            
               if west box is active and not traversed
                  traverse west box
            }
            Last edited by Rabbit; Dec 31 '13, 07:09 PM. Reason: Fixed some logic errors in pseudo code.

            Comment

            Working...