Initial code for boids v2

Too many new features to list! But here are the biggies:
- Boids can move on air and/or land, or climb a goal object.
- Proper interaction with collision objects.
	* Closest collision object in negative z direction is considered as ground.
	* Other collision objects are obstacles and boids collide with them.
- Boid behavior rules are now added to a dynamic list.
	* Many new rules and many still not implemented.
	* Different rule evaluation modes (fuzzy, random, average).
- Only particle systems defined by per system "boid relations" are considered for simulation of that system.
	* This is in addition to the boids own system of course.
	* Relations define other systems as "neutral", "friend" or "enemy".
- All effectors now effect boid physics, not boid brains.
	* This allows forcing boids somewhere.
	* Exception to this is new "boid" effector, which defines boid predators (positive strength) and goals (negative strength).
	
Known issue:
- Boid health isn't yet stored in pointcache so simulations with "fight" rule are not be read from cache properly.
- Object/Group visualization object's animation is not played in "particle time". This is definately the wanted behavior, but isn't possible with the current state of dupliobject code.

Other new features:
- Particle systems can now be named separately from particle settings.
	* Default name for particle settings is now "ParticleSettings" instead of "PSys"
- Per particle system list of particle effector weights.
	* Enables different effection strengths for particles from different particle systems with without messing around with effector group setting.

Other code changes:
- KDTree now supports range search as it's needed for new boids.
- "Keyed particle targets" renamed as general "particle targets", as they're needed for boids too. (this might break some files saved with new keyed particles)

Bug fixes:
- Object & group visualizations didn't work.
- Interpolating pointcache didn't do rotation.

2 files changed, 115 insertions, 13 deletions

diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index f258746dafe..c43c720bad0 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -53,6 +53,7 @@
 #include "DNA_armature_types.h"
 #include "DNA_ID.h"
 #include "DNA_actuator_types.h"
+#include "DNA_boid_types.h"
 #include "DNA_brush_types.h"
 #include "DNA_camera_types.h"
 #include "DNA_cloth_types.h"
@@ -2990,6 +2991,29 @@ static void lib_link_particlesettings(FileData *fd, Main *main)
 			part->dup_group = newlibadr(fd, part->id.lib, part->dup_group);
 			part->eff_group = newlibadr(fd, part->id.lib, part->eff_group);
 			part->bb_ob = newlibadr(fd, part->id.lib, part->bb_ob);
+			if(part->boids) {
+				BoidState *state = part->boids->states.first;
+				BoidRule *rule;
+				for(; state; state=state->next) {
+					rule = state->rules.first;
+				for(; rule; rule=rule->next)
+					switch(rule->type) {
+						case eBoidRuleType_Goal:
+						case eBoidRuleType_Avoid:
+						{
+							BoidRuleGoalAvoid *brga = (BoidRuleGoalAvoid*)rule;
+							brga->ob = newlibadr(fd, part->id.lib, brga->ob);
+							break;
+						}
+						case eBoidRuleType_FollowLeader:
+						{
+							BoidRuleFollowLeader *brfl = (BoidRuleFollowLeader*)rule;
+							brfl->ob = newlibadr(fd, part->id.lib, brfl->ob);
+							break;
+						}
+					}
+				}
+			}
 			part->id.flag -= LIB_NEEDLINK;
 		}
 		part= part->id.next;
@@ -3001,6 +3025,19 @@ static void direct_link_particlesettings(FileData *fd, ParticleSettings *part)
 	part->adt= newdataadr(fd, part->adt);
 	part->pd= newdataadr(fd, part->pd);
 	part->pd2= newdataadr(fd, part->pd2);
+
+	part->boids= newdataadr(fd, part->boids);
+
+	if(part->boids) {
+		BoidState *state;
+		link_list(fd, &part->boids->states);
+		
+		for(state=part->boids->states.first; state; state=state->next) {
+			link_list(fd, &state->rules);
+			link_list(fd, &state->conditions);
+			link_list(fd, &state->actions);
+		}
+	}
 }
 
 static void lib_link_particlesystems(FileData *fd, Object *ob, ID *id, ListBase *particles)
@@ -3015,10 +3052,10 @@ static void lib_link_particlesystems(FileData *fd, Object *ob, ID *id, ListBase
 		
 		psys->part = newlibadr_us(fd, id->lib, psys->part);
 		if(psys->part) {
-			KeyedParticleTarget *kpt = psys->keyed_targets.first;
+			ParticleTarget *pt = psys->targets.first;
 
-			for(; kpt; kpt=kpt->next)
-				kpt->ob=newlibadr(fd, id->lib, kpt->ob);
+			for(; pt; pt=pt->next)
+				pt->ob=newlibadr(fd, id->lib, pt->ob);
 
 			psys->target_ob = newlibadr(fd, id->lib, psys->target_ob);
 
@@ -3042,24 +3079,38 @@ static void lib_link_particlesystems(FileData *fd, Object *ob, ID *id, ListBase
 static void direct_link_particlesystems(FileData *fd, ListBase *particles)
 {
 	ParticleSystem *psys;
+	ParticleData *pa;
 	int a;
 
 	for(psys=particles->first; psys; psys=psys->next) {
 		psys->particles=newdataadr(fd,psys->particles);
+		
 		if(psys->particles && psys->particles->hair){
-			ParticleData *pa = psys->particles;
-			for(a=0; a<psys->totpart; a++, pa++)
+			for(a=0,pa=psys->particles; a<psys->totpart; a++, pa++)
 				pa->hair=newdataadr(fd,pa->hair);
 		}
+		
 		if(psys->particles && psys->particles->keys){
-			ParticleData *pa = psys->particles;
-			for(a=0; a<psys->totpart; a++, pa++) {
+			for(a=0,pa=psys->particles; a<psys->totpart; a++, pa++) {
 				pa->keys= NULL;
 				pa->totkey= 0;
 			}
 
 			psys->flag &= ~PSYS_KEYED;
 		}
+
+		if(psys->particles->boid) {
+			pa = psys->particles;
+			pa->boid = newdataadr(fd, pa->boid);
+			for(a=1,pa++; a<psys->totpart; a++, pa++)
+				pa->boid = (pa-1)->boid + 1;
+		}
+		else {
+			for(a=0,pa=psys->particles; a<psys->totpart; a++, pa++)
+				pa->boid = NULL;
+		}
+
+
 		psys->child=newdataadr(fd,psys->child);
 		psys->effectors.first=psys->effectors.last=0;
 
@@ -3076,7 +3127,7 @@ static void direct_link_particlesystems(FileData *fd, ListBase *particles)
 				direct_link_pointcache(fd, sb->pointcache);
 		}
 
-		link_list(fd, &psys->keyed_targets);
+		link_list(fd, &psys->targets);
 
 		psys->edit = 0;
 		psys->free_edit = NULL;
@@ -3089,6 +3140,8 @@ static void direct_link_particlesystems(FileData *fd, ListBase *particles)
 		psys->pointcache= newdataadr(fd, psys->pointcache);
 		if(psys->pointcache)
 			direct_link_pointcache(fd, psys->pointcache);
+
+		psys->tree = NULL;
 	}
 	return;
 }
@@ -3649,6 +3702,9 @@ static void direct_link_modifiers(FileData *fd, ListBase *lb)
 
 			surmd->dm = NULL;
 			surmd->bvhtree = NULL;
+			surmd->x = NULL;
+			surmd->v = NULL;
+			surmd->numverts = 0;
 		}
 		else if (md->type==eModifierType_Hook) {
 			HookModifierData *hmd = (HookModifierData*) md;
@@ -8541,7 +8597,7 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
 				psys = MEM_callocN(sizeof(ParticleSystem), "particle_system");
 				psys->pointcache = BKE_ptcache_add();
 
-				part = psys->part = psys_new_settings("PSys", main);
+				part = psys->part = psys_new_settings("ParticleSettings", main);
 				
 				/* needed for proper libdata lookup */
 				oldnewmap_insert(fd->libmap, psys->part, psys->part, 0);
diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c
index 958e8bb874b..9e5fbfc2598 100644
--- a/source/blender/blenloader/intern/writefile.c
+++ b/source/blender/blenloader/intern/writefile.c
@@ -93,6 +93,7 @@ Any case: direct data is ALWAYS after the lib block
 #include "DNA_armature_types.h"
 #include "DNA_action_types.h"
 #include "DNA_actuator_types.h"
+#include "DNA_boid_types.h"
 #include "DNA_brush_types.h"
 #include "DNA_camera_types.h"
 #include "DNA_cloth_types.h"
@@ -550,6 +551,39 @@ static void write_userdef(WriteData *wd)
 	}
 }
 
+static void write_boid_state(WriteData *wd, BoidState *state)
+{
+	BoidRule *rule = state->rules.first;
+	//BoidCondition *cond = state->conditions.first;
+
+	writestruct(wd, DATA, "BoidState", 1, state);
+
+	for(; rule; rule=rule->next) {
+		switch(rule->type) {
+			case eBoidRuleType_Goal:
+			case eBoidRuleType_Avoid:
+				writestruct(wd, DATA, "BoidRuleGoalAvoid", 1, rule);
+				break;
+			case eBoidRuleType_AvoidCollision:
+				writestruct(wd, DATA, "BoidRuleAvoidCollision", 1, rule);
+				break;
+			case eBoidRuleType_FollowLeader:
+				writestruct(wd, DATA, "BoidRuleFollowLeader", 1, rule);
+				break;
+			case eBoidRuleType_AverageSpeed:
+				writestruct(wd, DATA, "BoidRuleAverageSpeed", 1, rule);
+				break;
+			case eBoidRuleType_Fight:
+				writestruct(wd, DATA, "BoidRuleFight", 1, rule);
+				break;
+			default:
+				writestruct(wd, DATA, "BoidRule", 1, rule);
+				break;
+		}
+	}
+	//for(; cond; cond=cond->next)
+	//	writestruct(wd, DATA, "BoidCondition", 1, cond);
+}
 /* TODO: replace *cache with *cachelist once it's coded */
 #define PTCACHE_WRITE_PSYS	0
 #define PTCACHE_WRITE_CLOTH	1
@@ -582,6 +616,15 @@ static void write_particlesettings(WriteData *wd, ListBase *idbase)
 			if (part->adt) write_animdata(wd, part->adt);
 			writestruct(wd, DATA, "PartDeflect", 1, part->pd);
 			writestruct(wd, DATA, "PartDeflect", 1, part->pd2);
+
+			if(part->boids && part->phystype == PART_PHYS_BOIDS) {
+				BoidState *state = part->boids->states.first;
+
+				writestruct(wd, DATA, "BoidSettings", 1, part->boids);
+
+				for(; state; state=state->next)
+					write_boid_state(wd, state);
+			}
 		}
 		part= part->id.next;
 	}
@@ -589,7 +632,7 @@ static void write_particlesettings(WriteData *wd, ListBase *idbase)
 static void write_particlesystems(WriteData *wd, ListBase *particles)
 {
 	ParticleSystem *psys= particles->first;
-	KeyedParticleTarget *kpt;
+	ParticleTarget *pt;
 	int a;
 
 	for(; psys; psys=psys->next) {
@@ -604,10 +647,13 @@ static void write_particlesystems(WriteData *wd, ListBase *particles)
 				for(a=0; a<psys->totpart; a++, pa++)
 					writestruct(wd, DATA, "HairKey", pa->totkey, pa->hair);
 			}
+
+			if(psys->particles->boid && psys->part->phystype == PART_PHYS_BOIDS)
+				writestruct(wd, DATA, "BoidData", psys->totpart, psys->particles->boid);
 		}
-		kpt = psys->keyed_targets.first;
-		for(; kpt; kpt=kpt->next)
-			writestruct(wd, DATA, "KeyedParticleTarget", 1, kpt);
+		pt = psys->targets.first;
+		for(; pt; pt=pt->next)
+			writestruct(wd, DATA, "ParticleTarget", 1, pt);
 
 		if(psys->child) writestruct(wd, DATA, "ChildParticle", psys->totchild ,psys->child);
 		writestruct(wd, DATA, "SoftBody", 1, psys->soft);